Problem Brief
Good Subsequences
OA
A subsequence of a given string is generated by deleting zero or more characters from a string, then concatenating the remaining characters. A good subsequence is one where the frequency of each character is the same. Given a string that consists of n Latin letters, determine how many good subsequences it contains. Since the answer can be quite large, compute its modulo (10^9 + 7).
Note: An empty subsequence is not a good subsequence.
Function Description
Complete the function countGoodSubsequences in the editor below.
countGoodSubsequences has the following parameter(s):
- string word: a string that consists of only lowercase Latin letters
Returns
int: the number of good subsequences modulo (10^9 + 7)
1Example 1
Input
word = "abca"
Output
12
Explanation
A total of 15 non-empty subsequences can be formed from words: "a", "a", "aa", "ab", "aba", "abc", "abca", "ac", "aca", "b", "ba", "bc", "bca", "c", and "ca".
The only subsequences that are not good are "aba," "aca," and "abca" as the frequency of character "a" is 2, and every other character is 1.
The total number of good subsequences = 15 - 3 = 12 and answer to the above example = 12 modulo (109+7) = 12.
2Example 2
Input
word = "abcd"
Output
15
Explanation
All of the non-empty subsequences are good subsequences. They are "a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", and "d".
Constraints
Limits and guarantees your solution can rely on.
- 1 ≤ length of word ≤ 10^5
- word[i] is in the range [a-z]