Given a string s, return the number of non-empty good subsequences of s. A subsequence is good if every character in it appears the same number of times. Answer modulo 10^9 + 7.

Examples

Example 1:

Input: s = "aabb"
Output: 11

Good subsequences:
  k=1: "a","a","b","b","ab","ab","ab","ab" → 8
  k=2: "aa","bb","aabb" → 3
  Total = 11

Example 2:

Input: s = "leet"
Output: 7

freq: l=1, e=2, t=1
  k=1: "l","e","e","t","le","lt","et","le","lt","et" ...
  (counted via formula below)

Constraints

  • 1 <= s.length <= 10^4
  • s consists of lowercase English letters only

Thinking Process

Why Brute Force Fails

Enumerating all 2^n - 1 non-empty subsequences and checking each one is exponential. We need a combinatorial approach.

The Key Insight

Instead of generating subsequences, fix a target frequency k and count how many subsequences have every chosen character appearing exactly k times.

For a fixed k:

  • For each character c with freq[c] >= k, we can either include it (choose exactly k of its freq[c] occurrences: binom{freq[c]}{k} ways) or exclude it entirely (1 way)
  • Characters with freq[c] < k must be excluded

So the total for a given k:

$text{ways}(k) = prod_{text{all chars } c} left(1 + binom{freq[c]}{k} · [freq[c] ge k]right) - 1

The -1 removes the empty subsequence (where every character is excluded).

Final Answer

text{answer} = sum_{k=1}^{max_freq} text{ways}(k)

Efficient Combinations

We need \binom{n}{k} for various n, k up to \max_freq. Using a Pascal table would be O(n^2) memory, which can blow up for large frequencies.

Instead, precompute factorials and use Fermat’s little theorem for modular inverse:

binom{n}{k} = frac{n!}{k! · (n-k)!} = n! · (k!)^{-1} · ((n-k)!)^{-1} pmod{10^9+7}

Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Solution

class Solution {
public:
    static const int MOD = 1e9 + 7;

    long long modPow(long long a, long long b) {
        long long res = 1;
        while (b) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    int countGoodSubsequences(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;

        int max_f = 0;
        for (auto& [c, f] : freq) max_f = max(max_f, f);

        vector<long long> fact(max_f + 1, 1), invfact(max_f + 1, 1);
        for (int i = 1; i <= max_f; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        invfact[max_f] = modPow(fact[max_f], MOD - 2);
        for (int i = max_f - 1; i >= 0; i--) {
            invfact[i] = invfact[i + 1] * (i + 1) % MOD;
        }

        auto comb = [&](int n, int k) {
            return fact[n] % MOD * invfact[k] % MOD * invfact[n - k] % MOD;
        };

        long long result = 0;
        for (int k = 1; k <= max_f; k++) {
            long long ways = 1;
            for (auto& [c, f] : freq) {
                if (f >= k) {
                    ways = ways * (1 + comb(f, k)) % MOD;
                }
            }
            ways = (ways - 1 + MOD) % MOD;
            result = (result + ways) % MOD;
        }
        return result;
    }
};

Solution Explanation

Approach: Two pointers on string (this problem)

Key idea: ### Why Brute Force Fails

How the code works:

  • For each character c with freq[c] >= k, we can either include it (choose exactly k of its freq[c] occurrences: \binom{freq[c]}{k} ways) or exclude it entirely (1 way)
  • Characters with freq[c] < k must be excluded

Walkthrough — input s = "aabb", expected output 11:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

Time: O(\text{maxFreq} \times |\Sigma|) where |\Sigma| \le 26 · Space: O(\text{maxFreq}) for factorial arrays## Walk-through: s = "aabb"

Why Not Pascal’s Triangle?

For inputs like "jjjjjj..." (single character, frequency 10^4), a Pascal table would need O(n^2) space – up to 10^8 entries. The factorial + modular inverse approach uses only O(n) space and computes each \binom{n}{k} in O(1).

Approach Space Per-query
Pascal’s triangle O(n^2) O(1)
Factorial + mod inverse O(n) O(1)

Common Mistakes

  • Forgetting the -1: The product includes the case where every character is excluded (empty subsequence), which must be subtracted
  • Not clamping combinations: Only characters with freq[c] >= k contribute; others must be skipped (their factor is just 1)
  • Using Pascal table for large n: Causes MLE; always use factorial arrays with Fermat inverse
  • Missing modular arithmetic: Intermediate products can overflow without % MOD at each step

Key Takeaways

  • “Fix a parameter and count” is a powerful combinatorial strategy – here we fix the target frequency k
  • For each character, the choice is binary: include (choose k copies) or exclude – giving a product formula
  • Modular inverse via Fermat’s little theorem (a^{-1} \equiv a^{p-2} \pmod{p}) is essential for efficient \binom{n}{k} under modulo
  • Grouping by frequency is a clean optimization when characters share the same count

References

Template Reference