Count and return the number of good subsequences in the given string s. You may return the modulo
A subsequence is a sequence formed from another sequence by deleting some or no elements while keeping the order of the remaining elements unchanged.
A good subsequence is a subsequence of a string if it is not empty and the frequency of each character is the same.
Constraints:
s.length
s will only contain lowercase English characters.
The solution to this problem involves calculating the combinations. We will start by calculating the frequency of each character and then iterate over the frequencies, from 1 to the highest frequency of any character. We will count subsequences where each character appears for some or all of its frequency, i.e., calculating combinations. The count is summed up in each iteration, and after the loop terminates, 1 is deducted from the final count. The reason for deducting 1 is that the empty subsequence will also be counted. Because empty subsequence does not qualify as a good subsequence, we will remove its count from the final calculation.
Computing the combinations is a typical
Because calculating the factorial[i] requires calculating the [factorial[i-1]..factorial[2]] again and again, therefore we will use dynamic programming to calculate the factorial[i] by multiplying i only with factorial[i — 1]. That is, we will reuse the existing results instead of calculating them again.
The algorithm to solve this problem is as follows:
Initialize two arrays: factorials and inverses of size n + 1, an integer array, character_frequencies, of the same size to count the frequencies of each character and an integer variable finalCount with
Start a loop from n + 1. Inside the loop, compute the factorial and inverses of each ith number and store it in factorials[i] and inverses[i], respectively.
Start a loop from
Count and return the number of good subsequences in the given string s. You may return the modulo
A subsequence is a sequence formed from another sequence by deleting some or no elements while keeping the order of the remaining elements unchanged.
A good subsequence is a subsequence of a string if it is not empty and the frequency of each character is the same.
Constraints:
s.length
s will only contain lowercase English characters.
The solution to this problem involves calculating the combinations. We will start by calculating the frequency of each character and then iterate over the frequencies, from 1 to the highest frequency of any character. We will count subsequences where each character appears for some or all of its frequency, i.e., calculating combinations. The count is summed up in each iteration, and after the loop terminates, 1 is deducted from the final count. The reason for deducting 1 is that the empty subsequence will also be counted. Because empty subsequence does not qualify as a good subsequence, we will remove its count from the final calculation.
Computing the combinations is a typical
Because calculating the factorial[i] requires calculating the [factorial[i-1]..factorial[2]] again and again, therefore we will use dynamic programming to calculate the factorial[i] by multiplying i only with factorial[i — 1]. That is, we will reuse the existing results instead of calculating them again.
The algorithm to solve this problem is as follows:
Initialize two arrays: factorials and inverses of size n + 1, an integer array, character_frequencies, of the same size to count the frequencies of each character and an integer variable finalCount with
Start a loop from n + 1. Inside the loop, compute the factorial and inverses of each ith number and store it in factorials[i] and inverses[i], respectively.
Start a loop from