Skip to main content
Talentd

Count the Number of Good Subsequences - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableMathStringCombinatorics5 min readAsked at: NVIDIA, Palantir, UKG +1
Practice this problem

Problem Statement

A subsequence of a string is good if it is not empty and the frequency of each one of its characters is the same.

Given a string s, return the number of good subsequences of s. Since the answer may be too large, return it modulo 109 + 7.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

 

Example 1:

Input: s = "aabb"
Output: 11
Explanation: The total number of subsequences is 24. There are five subsequences which are not good: "aabb", "aabb", "aabb", "aabb", and the empty subsequence. Hence, the number of good subsequences is 24-5 = 11.

Example 2:

Input: s = "leet"
Output: 12
Explanation: There are four subsequences which are not good: "leet", "leet", "leet", and the empty subsequence. Hence, the number of good subsequences is 24-4 = 12.

Example 3:

Input: s = "abcd"
Output: 15
Explanation: All of the non-empty subsequences are good subsequences. Hence, the number of good subsequences is 24-1 = 15.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of only lowercase English letters.

Approach Overview

Problem Overview: Given a string s, count the number of non-empty subsequences where every distinct character appears the same number of times. A subsequence is formed by deleting characters without changing order, and the result should count all valid combinations.

Approach 1: Subsequence Enumeration with Frequency Validation (Exponential Time)

Generate every possible subsequence and check whether all characters appear the same number of times. For each generated subsequence, build a frequency map and verify that every count matches. This brute force approach relies heavily on string processing and a hash table for frequency checks. Since a string of length n has 2^n subsequences, the time complexity becomes O(2^n * n) and space complexity is O(n) for storing subsequences and frequency maps. This method only works for very small inputs but clarifies the definition of a "good" subsequence.

Approach 2: Frequency Counting + Combinatorics (Optimal)

Instead of generating subsequences directly, first count how many times each character appears. Suppose a character appears f times. If every chosen character must appear exactly k times in a valid subsequence, then you can choose C(f, k) ways to pick those positions. Iterate over all possible values of k from 1 to the maximum frequency in the string. For each k, multiply the choices across characters using (C(freq[i], k) + 1), where +1 represents skipping that character entirely. Subtract 1 at the end to remove the empty selection. This converts the problem into a pure combinatorics counting task.

Precompute combinations using factorials and modular inverses so each C(n, k) lookup is constant time. Since the alphabet size is small (26 lowercase letters), each iteration multiplies at most 26 values. The total time complexity becomes O(26 * maxFreq) and space complexity is O(n) for factorial precomputation. This approach avoids explicit subsequence generation and directly counts valid combinations.

Recommended for interviews: Interviewers expect the combinatorics approach. Starting with the brute force explanation shows you understand the definition of a good subsequence. Transitioning to frequency counting and C(n, k) reasoning demonstrates strong problem-solving skills and familiarity with counting techniques often used in medium-to-hard string problems.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Subsequence EnumerationO(2^n * n)O(n)Conceptual understanding or very small strings
Frequency Counting + CombinatoricsO(26 * maxFreq)O(n)General case and interview-expected optimal solution

Video Solution

Count the Number of Good Subsequences - LeetCode Premium • LeetCode Україна • 1,293 views views

Frequently Asked Questions

Is Count the Number of Good Subsequences easy or hard?
This problem is generally classified as medium difficulty. The challenge is recognizing that enumerating subsequences is infeasible and converting the problem into a combinatorics counting task based on character frequencies.
Count the Number of Good Subsequences Python/Java solution
The typical implementation counts character frequencies, precomputes factorials and modular inverses, and iterates possible frequency values k. For each k, compute the product of (C(freq[i], k) + 1) across characters and subtract one. The same logic works in Python, Java, C++, and Go using modular arithmetic.
How to solve Count the Number of Good Subsequences in O(n)?
First count character frequencies using a hash map or fixed array of size 26. Precompute factorials and inverse factorials to evaluate C(n, k). For each possible frequency k from 1 to maxFreq, multiply (C(freq[i], k) + 1) for every character and subtract one to exclude the empty subsequence.
What is the best approach for Count the Number of Good Subsequences?
The most efficient approach uses frequency counting combined with combinatorics. Count occurrences of each character, iterate possible frequencies k, and compute combinations C(freq, k) for each character. Multiply choices across characters and subtract the empty case. This runs in O(26 * maxFreq) time with O(n) preprocessing for factorials.
Is Count the Number of Good Subsequences asked at Google/Amazon/Meta?
Problems involving combinatorics, frequency counting, and subsequence counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine hash tables with combinatorial counting are common medium-level interview questions.
What data structure is used in Count the Number of Good Subsequences?
A frequency map (often an array of size 26 for lowercase letters) stores character counts. The algorithm also relies on combinatorics utilities such as factorial and inverse factorial arrays to compute binomial coefficients efficiently.
What is the time complexity of Count the Number of Good Subsequences?
The optimal solution runs in O(26 * maxFreq) time, where maxFreq is the maximum frequency of any character in the string. Combination values are computed using precomputed factorials and modular inverses, which require O(n) preprocessing space and time.

Ready to solve this problem?

Practice Count the Number of Good Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Ways to Build Rooms in an Ant Colony

Next

Number of Music Playlists