Watch the video solution for Count the Number of Good Subsequences, a medium level problem involving Hash Table, Math, String. This walkthrough by LeetCode Україна has 1,275 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 is24.There are five subsequences which are not good: "aabb", "aabb", "aabb", "aabb", and the empty subsequence. Hence, the number of good subsequences is24-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 <= 104s consists of only lowercase English letters.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Subsequence Enumeration | O(2^n * n) | O(n) | Conceptual understanding or very small strings |
| Frequency Counting + Combinatorics | O(26 * maxFreq) | O(n) | General case and interview-expected optimal solution |