• # 115 Distinct Subsequences C++ DP

Given a string S and a string T, count the number of distinct subsequences of S which equals T.
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.

### Solution

#### DP

Let `dp[n]` represent the count of prefix `T[0..n]` seen so far in `S`
Initial: `dp[*] = 0`

Recurrance:
`dp[n]` depends on `dp[n-1]` and `dp[n]`

To illustrate consider this example:
`S="RRABAB"`, `T="RAB"`
initially: `dp = [0, 0, 0] #[R A B]`
Lets iterate over `S`

``````s='R'  => dp = [1 0 0]
s='R'  => dp = [2 0 0]   # We have already seen the prefix 'R' so add one more
s='A'  => dp = [2 2 0]   # We have seen 2 R's and we see one A so 2 RA's are possible
s='B'  => dp = [2 2 2]   # 2 RA's seen earlier + B => 2 RAB's
s='A'  => dp = [2 4 2]   # 2 RA's seen earlier + 2 R's before this A => 4RAs
s='B'  => dp = [2 4 6]   # 2 RAB's seen earlier + 4 RA's before this B => 6RABs
``````

This can be summarised in this relationship for each iteration:
`dp[n] = dp[n] + dp[n-1]`

With repeating characters in `T` the key is to apply the relationship from the farthest character towards the earlier character.

``````S="RRAABAB"
T="RAAB"

-  [0 0 0 0]
R  [1 0 0 0]
R  [2 0 0 0]
A  [2 2 0 0]  # 'A' at 2 followed by 'A' at 1
A  [2 4 2 0]  # 'A' at 2 followed by 'A' at 1
B  [2 4 2 2]
A  [2 6 6 2]  # 'A' at 2 followed by 'A' at 1
B  [2 6 6 8]
``````

#### C++ Code

``````    int numDistinct(string s, string t) {
vector<int> dp(t.size(), 0);
for(auto c: s)
for(auto pos = t.size(); pos and (pos = t.find_last_of(c, pos-1))!=string::npos;)
dp[pos] += pos?dp[pos-1]:1;
return dp[t.size()-1];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.