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

The task is to find the count of distinct subsequences in a given string.

Use dynamic programming to solve the problem.
Create a 2D array to store the count of distinct subsequences for each prefix of the string.
Initialize the first row of the array with 1, as there is only one subsequence of an empty string.
For each character in the string, calculate the count of distinct subsequences by considering two cases: including the current character and excluding the current character.
The count of distinct subsequences including the current character is the sum of the count of distinct subsequences for the previous prefix and the count of distinct subsequences for the previous prefix without the current character.
The count of distinct subsequences excluding the current character is the same as the count of distinct subsequences for the previous prefix.
Return the last element of the last row of the array as the result.