Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Distinct Subsequences

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
50 upvotes
Asked in companies
UberGoogleMicrosoft

Problem statement

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.  
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample input 1:
2
abcd
dad 
Sample output 1:
16
7
Explanation
For test case 1: 


Distinct subsequence are: {“”}, {a}, {b}, {ab}, {c}, {ac}, {bc}, {abc}, {d}, {ad}, {bd}, {abd}, {cd}, {acd}, {bcd} and {abcd}. Thus, the answer will be 16. 

For test case 2:

Distinct subsequences are: {“”}, {d}, {a}, {da}, {dd}, {ad} and {dad}. Thus, the answer is 7.    

For better understanding, let us take all the subsequences of string dad. They will be: 

{“ ”}, {d}, {a}, {da}, {d}, {dd}, {ad} and {dad}
Now, {d} occurs twice and thus we will count it only once. 
Sample input 2:
2
xyzpqrs
abba
Sample output 2:
128
11
Full screen
Console