Facebook Pixel

2539. Count the Number of Good Subsequences 🔒

MediumHash TableMathStringCombinatoricsCounting
Leetcode Link

Problem Description

Given a string s, you need to count the number of good subsequences that can be formed from it.

A subsequence is good if:

  1. It is not empty
  2. Every character in the subsequence appears the same number of times

For example, if we have a subsequence "aabb", it's good because 'a' appears 2 times and 'b' appears 2 times (both have frequency 2).

A subsequence is formed by deleting some (possibly zero) characters from the original string without changing the relative order of the remaining characters.

Since the total count can be very large, return the answer modulo 10^9 + 7.

Key Points:

  • You need to find all possible subsequences where each distinct character appears exactly the same number of times
  • The subsequence must be non-empty
  • Characters maintain their relative order from the original string
  • The answer should be computed modulo 10^9 + 7

Example Understanding: If s = "aab", the good subsequences would include:

  • Single characters: "a", "a", "b" (each character appears once)
  • "aa" (character 'a' appears twice)
  • "ab" (both 'a' and 'b' appear once each)

The solution approach involves:

  1. Counting the frequency of each character in the string
  2. For each possible frequency i (from 1 to the maximum character count), calculating how many ways we can select characters such that each selected character appears exactly i times
  3. Using combinations C(v, i) to determine how many ways we can choose i occurrences from v total occurrences of a character
  4. Multiplying the possibilities for all characters and accumulating the result
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that a "good subsequence" requires all its characters to appear the same number of times. This means if we decide that each character should appear exactly k times in our subsequence, then we need to pick exactly k occurrences of each character we choose to include.

Let's think about this step by step:

  1. Fixed Frequency Pattern: Instead of trying to enumerate all possible subsequences directly, we can fix a frequency k and ask: "How many subsequences exist where each character appears exactly k times?"

  2. Character Independence: For a fixed frequency k, the choice of which occurrences to pick for each character is independent. If character 'a' appears 5 times in the original string and we want it to appear 2 times in our subsequence, we can choose any 2 of those 5 positions - that's C(5, 2) ways.

  3. Optional Inclusion: Not every character needs to be in our subsequence. A character can either:

    • Not appear at all (1 way to do this)
    • Appear exactly k times (which is C(count[char], k) ways if the character appears at least k times in the original string)

  4. Multiplication Principle: Since choices for different characters are independent, we multiply the number of ways for each character. For each character with count v:

    • If v >= k: We have C(v, k) + 1 choices (either pick k occurrences or pick none)
    • If v < k: We have only 1 choice (don't include this character at all)

  5. Iterating Over All Frequencies: We need to try all possible frequencies from 1 to the maximum character count in the string. For each frequency k, we calculate the total number of valid subsequences and sum them up.

  6. Avoiding Empty Subsequence: When we multiply (C(v, k) + 1) for all characters, we're counting the case where we don't pick any character at all (the empty subsequence). So we subtract 1 from each frequency's contribution to exclude this case.

The precomputed factorials and their modular inverses are used to efficiently calculate combinations modulo 10^9 + 7 using the formula: C(n, k) = n! / (k! * (n-k)!).

Learn more about Math and Combinatorics patterns.

Solution Approach

The implementation uses precomputation and combinatorics to efficiently count good subsequences:

1. Precomputation of Factorials and Modular Inverses:

N = 10001
MOD = 10**9 + 7
f = [1] * N  # f[i] stores i! mod MOD
g = [1] * N  # g[i] stores the modular inverse of i! mod MOD
  • Arrays f and g are precomputed up to size N = 10001
  • f[i] stores i! modulo MOD
  • g[i] stores the modular inverse of i! using Fermat's Little Theorem: inverse(a) = a^(MOD-2) mod MOD

2. Combination Function:

def comb(n, k):
    return f[n] * g[k] * g[n - k] % MOD
  • Calculates C(n, k) = n! / (k! * (n-k)!) using precomputed values
  • Uses modular arithmetic to avoid overflow

3. Main Algorithm:

def countGoodSubsequences(self, s: str) -> int:
    cnt = Counter(s)  # Count frequency of each character
    ans = 0
  • First, count the frequency of each character using Counter
  • Initialize answer to 0

4. Iterate Through All Possible Frequencies:

for i in range(1, max(cnt.values()) + 1):
    x = 1
    for v in cnt.values():
        if v >= i:
            x = x * (comb(v, i) + 1) % MOD
  • For each possible frequency i from 1 to the maximum character count
  • For each character with count v:
    • If v >= i: multiply by (C(v, i) + 1)
      • C(v, i): ways to choose i occurrences from v total
      • +1: option to not include this character at all
    • If v < i: implicitly multiply by 1 (character cannot appear i times)

5. Accumulate Results:

ans = (ans + x - 1) % MOD
  • Add x - 1 to the answer for this frequency
  • Subtract 1 to exclude the empty subsequence (where no character is selected)
  • Apply modulo to keep the result within bounds

6. Return Final Answer:

return ans

Time Complexity: O(n + m * k) where n is the length of string, m is the number of unique characters, and k is the maximum frequency of any character.

Space Complexity: O(N) for the precomputed arrays plus O(m) for the character frequency counter.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with s = "aabb".

Step 1: Count character frequencies

  • cnt = {'a': 2, 'b': 2}
  • Maximum frequency = 2

Step 2: Try each possible frequency (1 to 2)

For frequency i = 1:

  • Each character should appear exactly 1 time in the subsequence
  • For character 'a' (appears 2 times):
    • Ways to choose 1 occurrence from 2: C(2,1) = 2
    • Options: pick 1 occurrence (2 ways) or skip (1 way) = 2 + 1 = 3 ways
  • For character 'b' (appears 2 times):
    • Ways to choose 1 occurrence from 2: C(2,1) = 2
    • Options: pick 1 occurrence (2 ways) or skip (1 way) = 2 + 1 = 3 ways
  • Total combinations: 3 × 3 = 9
  • Subtract 1 (empty subsequence): 9 - 1 = 8
  • Valid subsequences: "a" (first a), "a" (second a), "b" (first b), "b" (second b), "ab" (4 different combinations of choosing which 'a' and which 'b')

For frequency i = 2:

  • Each character should appear exactly 2 times in the subsequence
  • For character 'a' (appears 2 times):
    • Ways to choose 2 occurrences from 2: C(2,2) = 1
    • Options: pick 2 occurrences (1 way) or skip (1 way) = 1 + 1 = 2 ways
  • For character 'b' (appears 2 times):
    • Ways to choose 2 occurrences from 2: C(2,2) = 1
    • Options: pick 2 occurrences (1 way) or skip (1 way) = 1 + 1 = 2 ways
  • Total combinations: 2 × 2 = 4
  • Subtract 1 (empty subsequence): 4 - 1 = 3
  • Valid subsequences: "aa", "bb", "aabb"

Step 3: Sum all results

  • Total = 8 + 3 = 11

The answer is 11 good subsequences.

Solution Implementation

1from collections import Counter
2
3# Precompute factorials and inverse factorials for combinatorial calculations
4N = 10001
5MOD = 10**9 + 7
6
7# factorial[i] = i! mod MOD
8factorial = [1] * N
9# inverse_factorial[i] = (i!)^(-1) mod MOD
10inverse_factorial = [1] * N
11
12# Precompute factorials and their modular inverses
13for i in range(1, N):
14    factorial[i] = factorial[i - 1] * i % MOD
15    # Using Fermat's Little Theorem: a^(-1) ≡ a^(p-2) (mod p) where p is prime
16    inverse_factorial[i] = pow(factorial[i], MOD - 2, MOD)
17
18
19def comb(n, k):
20    """
21    Calculate binomial coefficient C(n, k) mod MOD.
22  
23    Args:
24        n: Total number of items
25        k: Number of items to choose
26  
27    Returns:
28        C(n, k) mod MOD
29    """
30    return factorial[n] * inverse_factorial[k] * inverse_factorial[n - k] % MOD
31
32
33class Solution:
34    def countGoodSubsequences(self, s: str) -> int:
35        """
36        Count the number of good subsequences in string s.
37        A good subsequence has equal frequency for all characters in it.
38      
39        Args:
40            s: Input string
41      
42        Returns:
43            Number of good subsequences modulo MOD
44        """
45        # Count frequency of each character in the string
46        char_frequency = Counter(s)
47      
48        # Initialize result
49        result = 0
50      
51        # Try each possible frequency (each character appears exactly i times)
52        max_frequency = max(char_frequency.values())
53      
54        for target_freq in range(1, max_frequency + 1):
55            # Count ways to form subsequences where each character appears exactly target_freq times
56            ways = 1
57          
58            for char_count in char_frequency.values():
59                if char_count >= target_freq:
60                    # For this character, we can either:
61                    # 1. Include it (choose target_freq occurrences from char_count)
62                    # 2. Exclude it (multiply by 1)
63                    # Total ways = C(char_count, target_freq) + 1
64                    ways = ways * (comb(char_count, target_freq) + 1) % MOD
65          
66            # Subtract 1 to exclude the empty subsequence
67            result = (result + ways - 1) % MOD
68      
69        return result
70
1class Solution {
2    // Constants for array size and modulo value
3    private static final int MAX_SIZE = 10001;
4    private static final int MOD = (int) 1e9 + 7;
5  
6    // Precomputed factorials and their modular inverses
7    private static final long[] factorials = new long[MAX_SIZE];
8    private static final long[] inverseFactorials = new long[MAX_SIZE];
9
10    // Static block to precompute factorials and their modular inverses
11    static {
12        factorials[0] = 1;
13        inverseFactorials[0] = 1;
14      
15        // Compute factorials modulo MOD
16        for (int i = 1; i < MAX_SIZE; ++i) {
17            factorials[i] = factorials[i - 1] * i % MOD;
18            // Compute modular inverse using Fermat's Little Theorem
19            inverseFactorials[i] = modularPower(factorials[i], MOD - 2, MOD);
20        }
21    }
22
23    /**
24     * Computes (base^exponent) % modulo using fast exponentiation
25     * @param base the base number
26     * @param exponent the power to raise the base to
27     * @param modulo the modulo value
28     * @return (base^exponent) % modulo
29     */
30    public static long modularPower(long base, long exponent, long modulo) {
31        long result = 1;
32      
33        while (exponent != 0) {
34            // If exponent is odd, multiply result by base
35            if ((exponent & 1) == 1) {
36                result = result * base % modulo;
37            }
38            // Square the base and halve the exponent
39            exponent >>= 1;
40            base = base * base % modulo;
41        }
42      
43        return result;
44    }
45
46    /**
47     * Computes the binomial coefficient C(n, k) modulo MOD
48     * @param n total number of items
49     * @param k number of items to choose
50     * @return C(n, k) % MOD
51     */
52    public static long binomialCoefficient(int n, int k) {
53        // C(n, k) = n! / (k! * (n-k)!)
54        return (factorials[n] * inverseFactorials[k] % MOD) * inverseFactorials[n - k] % MOD;
55    }
56
57    /**
58     * Counts the number of good subsequences in the string
59     * A good subsequence has equal frequency for all characters present in it
60     * @param s the input string
61     * @return count of good subsequences modulo MOD
62     */
63    public int countGoodSubsequences(String s) {
64        // Count frequency of each character (26 lowercase letters)
65        int[] charFrequency = new int[26];
66        int maxFrequency = 1;
67      
68        // Calculate character frequencies and find maximum frequency
69        for (int i = 0; i < s.length(); ++i) {
70            int charIndex = s.charAt(i) - 'a';
71            charFrequency[charIndex]++;
72            maxFrequency = Math.max(maxFrequency, charFrequency[charIndex]);
73        }
74      
75        long totalCount = 0;
76      
77        // For each possible frequency k (1 to maxFrequency)
78        for (int targetFreq = 1; targetFreq <= maxFrequency; ++targetFreq) {
79            long subsequenceCount = 1;
80          
81            // For each character, calculate ways to choose targetFreq occurrences
82            for (int charIndex = 0; charIndex < 26; ++charIndex) {
83                if (charFrequency[charIndex] >= targetFreq) {
84                    // Either include this character (choose targetFreq from available)
85                    // or exclude it (multiply by 1, implicit in the +1)
86                    long waysToChoose = binomialCoefficient(charFrequency[charIndex], targetFreq) + 1;
87                    subsequenceCount = subsequenceCount * waysToChoose % MOD;
88                }
89            }
90          
91            // Subtract 1 to exclude the empty subsequence
92            totalCount = (totalCount + subsequenceCount - 1) % MOD;
93        }
94      
95        return (int) totalCount;
96    }
97}
98
1class Solution {
2private:
3    static constexpr int MAX_N = 10001;
4    static constexpr int MOD = 1e9 + 7;
5    static long factorial[10001];
6    static long inverseFactorial[10001];
7  
8    // Fast modular exponentiation: computes (base^exponent) % modulo
9    static long modularPower(long base, long exponent, long modulo) {
10        long result = 1;
11        while (exponent != 0) {
12            // If exponent is odd, multiply result by base
13            if ((exponent & 1) == 1) {
14                result = result * base % modulo;
15            }
16            exponent >>= 1;  // Divide exponent by 2
17            base = base * base % modulo;  // Square the base
18        }
19        return result;
20    }
21  
22    // Static initialization block to precompute factorials and their modular inverses
23    static int initializeFactorials() {
24        factorial[0] = 1;
25        inverseFactorial[0] = 1;
26      
27        // Compute factorials: factorial[i] = i! % MOD
28        for (int i = 1; i < MAX_N; ++i) {
29            factorial[i] = factorial[i - 1] * i % MOD;
30            // Compute modular inverse using Fermat's Little Theorem
31            // Since MOD is prime, inverse of factorial[i] = factorial[i]^(MOD-2) % MOD
32            inverseFactorial[i] = modularPower(factorial[i], MOD - 2, MOD);
33        }
34        return 0;
35    }
36  
37    static int dummy;  // Trigger static initialization
38  
39    // Compute binomial coefficient C(n, k) = n! / (k! * (n-k)!) % MOD
40    static int binomialCoefficient(int n, int k) {
41        return (factorial[n] * inverseFactorial[k] % MOD) * inverseFactorial[n - k] % MOD;
42    }
43  
44public:
45    int countGoodSubsequences(string s) {
46        // Count frequency of each character
47        int charFrequency[26]{};
48        int maxFrequency = 1;
49      
50        for (char& ch : s) {
51            int charIndex = ch - 'a';
52            charFrequency[charIndex]++;
53            maxFrequency = max(maxFrequency, charFrequency[charIndex]);
54        }
55      
56        long totalCount = 0;
57      
58        // For each possible length k (number of times each character appears)
59        for (int k = 1; k <= maxFrequency; ++k) {
60            long waysForCurrentLength = 1;
61          
62            // For each character in the alphabet
63            for (int charIdx = 0; charIdx < 26; ++charIdx) {
64                // If this character appears at least k times in the string
65                if (charFrequency[charIdx] >= k) {
66                    // We can either:
67                    // 1. Not include this character (1 way)
68                    // 2. Choose k occurrences from available occurrences (C(freq, k) ways)
69                    // Total: C(freq, k) + 1 ways
70                    waysForCurrentLength = (waysForCurrentLength * (binomialCoefficient(charFrequency[charIdx], k) + 1)) % MOD;
71                }
72            }
73          
74            // Subtract 1 to exclude the empty subsequence
75            totalCount = (totalCount + waysForCurrentLength - 1) % MOD;
76        }
77      
78        return totalCount;
79    }
80};
81
82// Static member definitions and initialization
83long Solution::factorial[10001];
84long Solution::inverseFactorial[10001];
85int Solution::dummy = Solution::initializeFactorials();
86
1// Constants
2const MAX_N = 10001;
3const MOD = 1000000007;
4
5// Precomputed factorial and inverse factorial arrays
6const factorial: number[] = new Array(MAX_N);
7const inverseFactorial: number[] = new Array(MAX_N);
8
9/**
10 * Fast modular exponentiation: computes (base^exponent) % modulo
11 * Uses binary exponentiation for O(log n) complexity
12 */
13function modularPower(base: number, exponent: number, modulo: number): number {
14    let result = 1;
15    base = base % modulo;
16  
17    while (exponent > 0) {
18        // If exponent is odd, multiply result by base
19        if ((exponent & 1) === 1) {
20            result = (result * base) % modulo;
21        }
22        exponent >>= 1;  // Divide exponent by 2
23        base = (base * base) % modulo;  // Square the base
24    }
25    return result;
26}
27
28/**
29 * Initialize factorials and their modular inverses
30 * Uses Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p) when p is prime
31 * Therefore, a^(-1) ≡ a^(p-2) (mod p)
32 */
33function initializeFactorials(): void {
34    factorial[0] = 1;
35    inverseFactorial[0] = 1;
36  
37    // Compute factorials: factorial[i] = i! % MOD
38    for (let i = 1; i < MAX_N; i++) {
39        factorial[i] = (factorial[i - 1] * i) % MOD;
40        // Compute modular inverse using Fermat's Little Theorem
41        // Since MOD is prime, inverse of factorial[i] = factorial[i]^(MOD-2) % MOD
42        inverseFactorial[i] = modularPower(factorial[i], MOD - 2, MOD);
43    }
44}
45
46// Initialize factorials on module load
47initializeFactorials();
48
49/**
50 * Compute binomial coefficient C(n, k) = n! / (k! * (n-k)!) % MOD
51 * Uses precomputed factorials and their inverses for O(1) calculation
52 */
53function binomialCoefficient(n: number, k: number): number {
54    return (((factorial[n] * inverseFactorial[k]) % MOD) * inverseFactorial[n - k]) % MOD;
55}
56
57/**
58 * Count all good subsequences where each character appears the same number of times
59 * @param s - Input string
60 * @returns Number of good subsequences modulo MOD
61 */
62function countGoodSubsequences(s: string): number {
63    // Count frequency of each character (26 lowercase letters)
64    const charFrequency: number[] = new Array(26).fill(0);
65    let maxFrequency = 1;
66  
67    // Calculate character frequencies and find maximum frequency
68    for (const char of s) {
69        const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
70        charFrequency[charIndex]++;
71        maxFrequency = Math.max(maxFrequency, charFrequency[charIndex]);
72    }
73  
74    let totalCount = 0;
75  
76    // For each possible length k (number of times each character appears in subsequence)
77    for (let k = 1; k <= maxFrequency; k++) {
78        let waysForCurrentLength = 1;
79      
80        // For each character in the alphabet
81        for (let charIdx = 0; charIdx < 26; charIdx++) {
82            // If this character appears at least k times in the string
83            if (charFrequency[charIdx] >= k) {
84                // We can either:
85                // 1. Not include this character in the subsequence (1 way)
86                // 2. Choose exactly k occurrences from available occurrences (C(freq, k) ways)
87                // Total ways: C(freq, k) + 1
88                waysForCurrentLength = (waysForCurrentLength * (binomialCoefficient(charFrequency[charIdx], k) + 1)) % MOD;
89            }
90        }
91      
92        // Subtract 1 to exclude the empty subsequence (when no characters are selected)
93        totalCount = (totalCount + waysForCurrentLength - 1 + MOD) % MOD;
94    }
95  
96    return totalCount;
97}
98

Time and Space Complexity

Time Complexity: O(N + m * u)

  • The preprocessing of factorials and their modular inverses takes O(N) time where N = 10001
  • In the main function countGoodSubsequences:
    • Creating the Counter takes O(n) where n is the length of string s
    • The outer loop runs from 1 to max(cnt.values()), which is at most n times
    • For each iteration i, the inner loop iterates through all unique characters in cnt, which is at most u (number of unique characters, bounded by 26 for lowercase letters)
    • Each comb(v, i) operation takes O(1) time since we're using precomputed factorials
    • Therefore, the main loop complexity is O(m * u) where m = max(cnt.values())
  • Overall: O(N + n + m * u) which simplifies to O(N + m * u) since N is a constant (10001) and typically dominates

Space Complexity: O(N + u)

  • Arrays f and g each use O(N) space where N = 10001
  • The Counter uses O(u) space where u is the number of unique characters in the string
  • Other variables use O(1) space
  • Overall: O(N + u) where N is constant (10001)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Modular Inverse Calculation

Pitfall: Using regular division instead of modular inverse when computing combinations, or incorrectly implementing the modular inverse.

# WRONG: Direct division doesn't work with modular arithmetic
def comb_wrong(n, k):
    return (factorial[n] // (factorial[k] * factorial[n-k])) % MOD

Solution: Use Fermat's Little Theorem to compute modular inverse properly:

def comb(n, k):
    return factorial[n] * inverse_factorial[k] * inverse_factorial[n - k] % MOD

2. Forgetting the Empty Subsequence Case

Pitfall: When all characters are excluded (each character contributes a factor of 1 from the "+1" term), we get a product of 1s, which represents the empty subsequence. Failing to subtract this leads to an off-by-one error.

# WRONG: Forgetting to subtract 1 for empty subsequence
for target_freq in range(1, max_frequency + 1):
    ways = 1
    for char_count in char_frequency.values():
        if char_count >= target_freq:
            ways = ways * (comb(char_count, target_freq) + 1) % MOD
    result = (result + ways) % MOD  # Missing -1 here!

Solution: Always subtract 1 after calculating the product:

result = (result + ways - 1) % MOD

3. Integer Overflow in Precomputation

Pitfall: Not applying modulo during factorial precomputation, causing integer overflow for large values.

# WRONG: Can cause overflow for large factorials
factorial = [1] * N
for i in range(1, N):
    factorial[i] = factorial[i - 1] * i  # Missing % MOD

Solution: Apply modulo at each step:

for i in range(1, N):
    factorial[i] = factorial[i - 1] * i % MOD

4. Incorrect Handling of Characters with Insufficient Count

Pitfall: Trying to compute combinations when char_count < target_freq, which would be invalid.

# WRONG: Computing invalid combinations
for char_count in char_frequency.values():
    ways = ways * (comb(char_count, target_freq) + 1) % MOD  # Error when char_count < target_freq

Solution: Only compute combinations when the character has enough occurrences:

for char_count in char_frequency.values():
    if char_count >= target_freq:
        ways = ways * (comb(char_count, target_freq) + 1) % MOD
    # Implicitly multiply by 1 when char_count < target_freq

5. Global Variable Collision

Pitfall: Using common variable names like f and g as global variables can cause issues in different environments or when the code is integrated into larger systems.

Solution: Use more descriptive names or encapsulate in a class:

# Better: More descriptive names
factorial = [1] * N
inverse_factorial = [1] * N

# Or encapsulate in a class
class CombinatoricsHelper:
    def __init__(self, n, mod):
        self.factorial = [1] * n
        self.inverse_factorial = [1] * n
        self.mod = mod
        self._precompute()
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More