Distinct Subsequences

Posted: 21 Oct, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given string 'S' of length 'N' that may contain duplicate alphabets. Your task is to return the count of distinct subsequences of it.

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.
Try Problem