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 10⁹ + 7, on a new line.

Constraints:

1

Question

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:

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 10⁹ + 7, on a new line.

Constraints:

1 <= T <= 10
1 <= N <= 10⁴

Note: The answer might be large, so return it modulo 10⁹ + 7.

Accepted Answer

Calculate the number of distinct subsequences in a string with possible duplicates.

Use dynamic programming to keep track of the count of distinct subsequences for each character in the string.
Consider the cases where the current character is included or excluded in the subsequence.
Handle duplicates by considering the previous occurrence of the character.
Return the count of distinct subsequences modulo 10^9 + 7.