Distinct Subsequences of a String

Given a string S of length N that may contain duplicate alphabets, your task is to compute the count of distinct subsequences of this string.

Example:

Input:

S = "deed"

Output:

11

Explanation:

The possible subsequences include: {""}, {"d"}, {"e"}, {"de"}, {"ee"}, {"dee"}, {"dd"}, {"ed"}, {"ded"}, {"eed"}, {"deed"}. Removing duplicates gives us 11 distinct subsequences.

Constraints:

1

Question

Distinct Subsequences of a String

Given a string S of length N that may contain duplicate alphabets, your task is to compute the count of distinct subsequences of this string.

Example:

Input:

S = "deed"

Output:

Explanation:

The possible subsequences include: {""}, {"d"}, {"e"}, {"de"}, {"ee"}, {"dee"}, {"dd"}, {"ed"}, {"ded"}, {"eed"}, {"deed"}. Removing duplicates gives us 11 distinct subsequences.

Constraints:

1 <= T <= 10
1 <= N <= 10^4

Note: The answer can be large, so return it modulo 10^9 + 7.

Input:

T (number of test cases)
string S (for each test case)

Output:

The count of distinct subsequences for each test case, displayed on separate lines.

Note: You do not need to print anything explicitly. Just implement the function to return the result.

Accepted Answer

Compute the count of distinct subsequences of a string with possible duplicates.

Use dynamic programming to keep track of distinct subsequences.
Consider the cases where the current character is included or excluded in the subsequence.
Use a hashmap to store the last occurrence index of each character to handle duplicates efficiently.

Asked in Microsoft Corporation