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

Problem of the day

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

```
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'.
```

```
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.
```

```
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.
```

```
2
abcd
dad
```

```
16
7
```

```
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.
```

```
2
xyzpqrs
abba
```

```
128
11
```