Count the Number of Good Subsequences

Count the Number of Good Subsequences

What is this problem about?

The Count the Number of Good Subsequences interview question defines a "good subsequence" as one where all unique characters in the subsequence appear with the exact same frequency.

For example, in the subsequence "aabbcc", every character ('a', 'b', 'c') appears twice. This is good. "aabbc" is not good because 'c' appears only once while 'a' and 'b' appear twice. You need to return the total count of such subsequences (modulo $10^9 + 7$).

Why is this asked in interviews?

Companies like Palantir and Nvidia use this to test combinatorics interview pattern and math proficiency. Unlike substrings, subsequences are not contiguous, meaning you can pick and choose characters. This problem requires iterating through all possible target frequencies (1 to the max frequency of any char) and calculating how many ways each character can contribute to that frequency.

Algorithmic pattern used

This is a Combinatorial Counting problem.

1. Count the frequencies of all characters in the original string.
2. Iterate through every possible frequency $F$ (from 1 up to the max frequency found).
3. For a fixed $F$:
   • For each character $c$ that appears $Count(c)$ times:
     • You can either not include $c$ in the subsequence (1 way).
     • Or include $c$ exactly $F$ times. There are $\binom{Count(c)}{F}$ ways to do this.
     • Total ways for this character at frequency $F$: $(1 + \binom{Count(c)}{F})$.
   • Multiply these "total ways" for all characters.
   • Subtract 1 (to exclude the empty subsequence where no characters were chosen).
4. Sum the results for all $F$.

Example explanation

s = "aabb"

• Freqs: a:2, b:2. Max F = 2.
• $F=1$:
  • 'a' ways: $1 + \binom{2}{1} = 3$.
  • 'b' ways: $1 + \binom{2}{1} = 3$.
  • Subsequences: $3 imes 3 - 1 = 8$. (Ways: a, a, b, b, ab, ab, ab, ab).
• $F=2$:
  • 'a' ways: $1 + \binom{2}{2} = 2$.
  • 'b' ways: $1 + \binom{2}{2} = 2$.
  • Subsequences: $2 imes 2 - 1 = 3$. (Ways: aa, bb, aabb). Total = $8 + 3 = 11$.

Common mistakes candidates make

• Misunderstanding "subsequence": Treating it like a substring and only looking at contiguous blocks.
• Missing combinations: Thinking there's only 1 way to pick 2 'a's from 3.
• Failing to use nCr with modulo: Not precomputing factorials and modular inverses.

Interview preparation tip

When a problem asks about subsequences and frequencies, the characters usually act independently. Calculate the ways for each character to contribute to a specific goal, multiply them, and then sum over all possible goals.