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

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