Good Subsequences
Nutanix● HardFULLTIMEOAProblem statement
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
countGoodSubsequences(word: String) → int
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
Example 1
word = "abca"return = 12A 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.
Example 2
word = "abcd"return = 15All 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".
Example 3
word = "aaa"return = 7Every non-empty subsequence contains only the character a, so the character frequencies are equal. There are 2^3 - 1 = 7 such subsequences.
Constraints
- 1 ≤ length of word ≤ 10^5
- word[i] is in the range [a-z]