### Question

Given a string **S** and a string **T**, count the number of distinct subsequences of **T** in **S**.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, `"ACE"`

is a subsequence of `"ABCDE"`

while `"AEC"`

is not).

Here is an example:

**S** = `"rabbbit"`

, **T** = `"rabbit"`

Return `3`

.

### Stats

Frequency | 2 |

Difficulty | 4 |

Adjusted Difficulty | 5 |

Time to use | -------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

**This is an extremely difficult DP question**, probably the most difficult DP on leetcode.

Normally, string matching question is best solved with DP, so is this question. The problem is how to construct the **Bellman equation** (also known as dynamic programming equation).

**Updated on June 24th**, I listed down one example using S = “abab” and T = “ab”.

{} | a | b | |
---|---|---|---|

{} | 1 | 0 | 0 |

a | 1 | 1 | 0 |

b | 1 | 1 | 1 |

a | 1 | 2 | 1 |

b | 1 | 2 | 3 |

### Solution

It took me a really long time to understand, until I read this blog.

Let W(i, j) stand for the number of subsequences of S(0, i) in T(0, j). If S.charAt(i) == T.charAt(j), W(i, j) = W(i-1, j-1) + W(i-1,j); Otherwise, W(i, j) = W(i-1,j).

Two code are posted below, realizing this solution with 2D and 1D array respectively (first code is better).

### Code

**First, DP code**

```
public int numDistinct(String S, String T) {
int m = S.length(), n = T.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i ++) {
for (int j = 0; j <= n; j ++) {
if (j == 0) dp[i][j] = 1;
else if (i == 0) dp[i][j] = 0;
else if (S.charAt(i-1) == T.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[m][n];
}
```

**Second, same solution but reduced 2-D array to 1-D**.

Code readability is reduced, however.

```
public int numDistinct(String S, String T) {
int m = S.length(), n = T.length();
int[] dp = new int[n + 1];
for (int i = 0; i <= m; i ++) {
for (int j = n; j >= 0; j --) {
if (j == 0)
dp[j] = 1;
else if (i == 0)
dp[j] = 0;
else if (S.charAt(i-1) == T.charAt(j-1))
dp[j] = dp[j-1] + dp[j];
}
}
return dp[n];
}
```