# Distinct Subsequences

## Guessing

Lets start with `rabbbit`

and `rabbit`

.

To make the problem easier, start from one char, `distinct subsequences`

of `rabbbit`

and `r`

.

`distinct subsequences`

below, by eyeball:

`r`

and`r`

has 1`distinct subsequences`

`a`

and`r`

has 0`distinct subsequences`

These two are easy to be understood.

`ra`

and`r`

has 1`distinct subsequences`

`rab`

and`r`

has 1`distinct subsequences`

`rabbbbbbbbbbbb`

and`r`

has 1`distinct subsequences`

These three show that `r`

plus any junk chars will not change `distinct subsequences`

`rr`

and`r`

has 2`distinct subsequences`

`rar`

and`r`

has 2`distinct subsequences`

`rara`

and`r`

has 2`distinct subsequences`

`rarar`

and`r`

has 3`distinct subsequences`

`rar`

and `r`

is same as `rr`

and `r`

, because `a`

there has nothing to do with the number of `distinct subsequences`

, it is a junk like above.

In another word, `rar`

and `r`

can be converted to `ra`

+ `r`

and `r`

, that is `1 + 1`

.

### Put them into table

the value `P[i][j]`

means that `S[0..i]`

and `T[0..j]`

has `P[i][j]`

`distinct subsequences`

.

the table with only one char

```
+---+---+---+---+---+---+---+---+
| | r | a | b | b | b | i | t |
+---+---+---+---+---+---+---+---+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
```

Enlarge the table

```
+---+---+---+---+---+---+---+---+
| | r | a | b | b | b | i | t |
+---+---+---+---+---+---+---+---+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| a | | | | | | | |
+---+---+---+---+---+---+---+---+
| b | | | | | | | |
+---+---+---+---+---+---+---+---+
| b | | | | | | | |
+---+---+---+---+---+---+---+---+
| i | | | | | | | |
+---+---+---+---+---+---+---+---+
| t | | | | | | | |
+---+---+---+---+---+---+---+---+
```

Some grids here are easy to be filled, the grids which `j > i`

.
That is, T is longer than S, there will be no `distinct subsequences`

.

```
+---+---+---+---+---+---+---+---+
| | r | a | b | b | b | i | t |
+---+---+---+---+---+---+---+---+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| a | 0 | | | | | | |
+---+---+---+---+---+---+---+---+
| b | 0 | 0 | | | | | |
+---+---+---+---+---+---+---+---+
| b | 0 | 0 | 0 | | | | |
+---+---+---+---+---+---+---+---+
| i | 0 | 0 | 0 | 0 | | | |
+---+---+---+---+---+---+---+---+
| t | 0 | 0 | 0 | 0 | 0 | | |
+---+---+---+---+---+---+---+---+
```

`j == i`

grids are easy too, the S and T must be the same if it wants to have 1 `distinct subsequences`

.

```
+---+---+---+---+---+---+---+---+
| | r | a | b | b | b | i | t |
+---+---+---+---+---+---+---+---+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| a | 0 | 1 | | | | | |
+---+---+---+---+---+---+---+---+
| b | 0 | 0 | 1 | | | | |
+---+---+---+---+---+---+---+---+
| b | 0 | 0 | 0 | 1 | | | |
+---+---+---+---+---+---+---+---+
| i | 0 | 0 | 0 | 0 | 0 | | |
+---+---+---+---+---+---+---+---+
| t | 0 | 0 | 0 | 0 | 0 | 0 | |
+---+---+---+---+---+---+---+---+
```

This pictrue is just encouraging you, as there is only a few grids left to be filled.

`rab`

and `ra`

This problem looks familiar. It is the `ra`

and `r`

.

as `b`

is a junk char, `rab`

should have the same number as `ra`

and `ra`

.

Then the table is like

```
+---+---+---+---+---+---+---+---+
| | r | a | b | b | b | i | t |
+---+---+---+---+---+---+---+---+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| b | 0 | 0 | 1 | | | | |
+---+---+---+---+---+---+---+---+
| b | 0 | 0 | 0 | 1 | | | |
+---+---+---+---+---+---+---+---+
| i | 0 | 0 | 0 | 0 | 0 | | |
+---+---+---+---+---+---+---+---+
| t | 0 | 0 | 0 | 0 | 0 | 0 | |
+---+---+---+---+---+---+---+---+
```

`rabb`

and `rab`

This time, add a new `b`

to both `rab`

and `ra`

.

#### Use the new `b`

in subsequences

This time they have same letter, `b`

, at the end. It is not a junk.

This time, remove `b`

from both S and T, then they become `rab`

and `ra`

.

that is, this will take `rab`

and `ra`

`distinct subsequences`

.

#### Dont use the new `b`

Treat `b`

as junk, it has `rab`

and `rab`

`distinct subsequences`

.

#### Sum up two choices

Use or not will result two set of `distinct subsequences`

, so sum them up.

`rabb`

and `rab`

= `rab`

and `ra`

+ `rab`

and `rab`

.

```
+---+---+---+---+---+---+---+---+
| | r | a | b | b | b | i | t |
+---+---+---+---+---+---+---+---+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| b | 0 | 0 | 1 | 2 | | | |
+---+---+---+---+---+---+---+---+
| b | 0 | 0 | 0 | 1 | | | |
+---+---+---+---+---+---+---+---+
| i | 0 | 0 | 0 | 0 | 0 | | |
+---+---+---+---+---+---+---+---+
| t | 0 | 0 | 0 | 0 | 0 | 0 | |
+---+---+---+---+---+---+---+---+
```

## General form

the grid `P[i][j]`

has 1 choice when `S[i] != T[j]`

, this only adds some junk chars.

```
P[i][j] = P[i - 1][j]
```

the grid `P[i][j]`

has 2 choice when `S[i] == T[j]`

```
P[i][j] =
P[i - 1][j] // adds as junk chars.
+
P[i - 1][j - 1] // use the new char in the new subsequence
```

Fill up the table and the bottom right grid is the answer.

### Source code *Read on Github*

```
1 public class Solution {
2 public int numDistinct(String S, String T) {
3
4
5 char[] s = S.toCharArray();
6 if(s.length == 0) return 0;
7
8 char[] t = T.toCharArray();
9 if(t.length == 0) return 0;
10
11 if(t.length > s.length) return 0;
12
13
14 int[][] P = new int[s.length][t.length];
15
16
17 P[0][0] = s[0] == t[0] ? 1 : 0;
18
19 for(int i = 1; i < s.length; i++){
20 P[i][0] = s[i] == t[0] ? 1 + P[i - 1][0] : P[i - 1][0];
21 }
22
23
24 for(int j = 1; j < t.length; j++){
25 for(int i = j; i < s.length; i++){
26
27 if(t[j] == s[i]){
28 // sum choices
29
30 P[i][j] = P[i - 1][j] + P[i - 1][j - 1];
31
32
33 } else {
34 // no choice
35 P[i][j] = P[i - 1][j];
36
37 }
38
39
40
41
42 }
43 }
44
45
46 return P[s.length - 1][t.length - 1];
47
48
49 }
50 }
```