
Distinct Subsequences Problem Statement
You are given a string 'S' of length 'N' which may include duplicate alphabets. Your goal is to calculate the number of distinct subsequences in the string.
Example:
Input:
"S" = "deed"
Output:
11
Explanation:
The possible subsequences are {""}, {"d"}, {"e"}, {"de"}, {"e"}, {"de"}, {"ee"}, {"dee"}, {"d"}, {"dd"}, {"ed"}, {"ded"}, {"ed"}, {"ded"}, {"eed"} and {"deed"}. After filtering duplicates, the distinct subsequences are: {""}, {"d"}, {"e"}, {"de"}, {"ee"}, {"dee"}, {"dd"}, {"ed"}, {"ded"}, {"eed"}, {"deed"}, resulting in 11 distinct subsequences.
Input:
The first line contains an integer 'T' denoting the number of test cases. Each of the following T lines contains a single string 'S'.
Output:
For each test case, output the count of distinct subsequences, modulo 109 + 7, on a new line.
Constraints:
1 <= T <= 10
1 <= N <= 104
Note: The answer might be large, so return it modulo 109 + 7.


Calculate the number of distinct subsequences in a string with possible duplicates.
Iterate through the string and keep track of the count of each character.
Use dynamic programming to calculate the num...read more

Top Kellton Software Engineer interview questions & answers
Popular interview questions of Software Engineer
Top HR questions asked in Kellton Software Engineer
Reviews
Interviews
Salaries
Users/Month