# Distinct Subsequences

Posted: 21 Oct, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### For example:

``````For the given string “deed” :
The possible subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“d”}, {“dd”}, {“ed”}, {“ded”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}.

As, {“d”}, {“e”}, {“de”}, {“ed”} and {“ded”} are repeated.

The distinct subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“dd”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}

Thus, the output will be 11.
``````

#### Note:

``````As the answer can be large, return your answer modulo 10^9  + 7.
``````
##### Input format:
``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case or query contains the string 'S'.
``````
##### Output format:
``````For each test case, print a single line containing the count of distinct subsequences modulo 10^9+7.

The output of each test case will be printed in a separate line.
``````

#### Note:

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 10 ^ 4

where 'T' is the number of test cases and 'N' is the length of the given string 'S'.

Time limit: 1 sec.
``````
Approach 1
• The IDea is to call a helper function so as to create all possible subsequences of the string which will contain:
• String CUR = the possible subsequence of the string.
• Int ID = the index of character which will either be included or excluded.
• We maintain a set to count the distinct subsequences, each time a new subsequence is created, we add it into the set. Remember, the set does not contain duplicate elements.
• We return the size of the set which is the count of distinct subsequences received from the helper function.

Algorithm:

void helper(STR, set, ID, CUR) :

• Base Case: if ID >= STR.size()’, this means that CUR is a possible subsequence, thus, add CUR to set and return.
• Call helper(STR, set, ID+1, CUR), this is where you exclude the current character.
• Call helper(STR, set, ID+1, CUR + STR[ID]), this is where you include the current character.

int distinctSubsequences(S) :

• Initialise an empty set.
• Call helper function, helper(STR, set, 0, “”).
• Return the size of the set.