string word: a string that consists of only lowercase Latin letters Returns int. the number of good subsequences modulo(10 9+7)Constraints -1≤length of word≤10 5- word[i] is in the range [a-z] - Input Format For Custom Testing The first and the only line consists of a string, word. - Sample Case 0 Sample Input For Custom TestingSTDIN abcd FUNCTION → word = "abcd" Sample Output 15 Explanation All of the non-empty subsequences are good subsequences. 2. 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 ofnLatin 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. Example word = "abca" A total of 15 non-empty subsequences can be formed from words. The only subsequences that are not good, are "aba", "aca" and "abca" as the frequencies of character "a" is 2 and every other character is 1. The total number of good subsequences=153=12and answer to the above example=12modulo(10 9+7)=12. Function Description Complete the function countGoodsubsequences in the editor below. countGoodsubsequences has the following parameter(s):

Using the knowledge in computational language in python it is possible to write a code that consists of only lowercase Latin letters Returns int.

Writting the code:

import bisect

mod = 10 ** 9 + 7

# HELPER FUNCTION:

# Calculating nCr % mod

def ncr(n, r):

# Initializing numerator and denominator to 1

numerator, denominator = 1, 1

# Iterating over [0, r - 1]

for i in range(r):

# Applying mod on each step

numerator = (numerator * (n - i)) % mod

denominator = (denominator * (i + 1)) % mod

# NOTE: modinverse of x and n is equal to mod of (x ^ (n - 2)) and n

return (numerator * pow(denominator, mod - 2, mod)) % mod

def countGoodSubsequences(word):

# Storing the length of the word

n = len(word)

# Building the frequency dictionary for the letters of the word

freqs = dict()

# Iterating over the letter word by word

for letter in word:

# Updating the frequency for that letter

# If there is no value for that letter, add a value of 0

if letter not in freqs:

freqs[letter] = 0

# Then, increment the value corresponding to that letter

freqs[letter] += 1

# Obtains the sorted counts of each letter

counts = sorted(freqs.values())

# Get the length of counts

lens = len(counts)

# Initialize the result to 0

res = 0

# Iterating over the frequencies [1, n]

for i in range(1, n + 1):

# Initializing the number of subsequences where each element has frequency i to 1

freq_i = 1

# bisect_left returns the first index of counts that is greater than or equal to i

# That is, it finds the first frequency that is atleast i

ind = bisect.bisect_left(counts, i)

# Now, for all the elements having frequencies,

# counts_1, counts_2, counts_3 ... such that counts_1, counts_2, counts_3 .... are all greater than or equal to i,

# there are a total of (1 + (counts_1) C (i) * (1 + (counts_2) C (i) ) ...... -1 subsequences, nCr is (n!) / (c! * r!)

# Iterating over [ind, lens) to count the total number of subsequences where each element has frequency i

for j in range(ind, lens):

# Updating freq_i

freq_i *= (1 + ncr(counts[j], i)) % mod

# Applying mod

freq_i %= mod

# Updating res

res += (freq_i - 1)

# Applying mod

res %= mod

return res

# Sample case

print(countGoodSubsequences("abca"))

See more about python at brainly.com/question/18502436

#SPJ1