How should I practice Good Subsequences?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Nutanix online assessment problems in FastPrep.

Is Good Subsequences associated with Nutanix?

FastPrep tags this as a Nutanix online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · String

Good Subsequences

Learn this problem

● Hard

NutanixFULLTIMEOA

Problem 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 = 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 (10⁹+7) = 12.

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".

Example 3

word = "aaa"return = 7

Every 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]