Problem · String
Good Subsequences
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.
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)
Examples
01 · Example 1
word = "abca" return = 12
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.
02 · Example 2
word = "abcd" return = 15
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
- 1 ≤ length of word ≤ 10^5
- word[i] is in the range [a-z]
More Nutanix problems
public int countGoodSubsequences(String word) {
// write your code here
}
word"abca"
expected12
sign in to submit