Dynamic Programming • Strings

Distinct Subsequences

Given two strings S and T, return the number of distinct subsequences of S which equal T.

Overview

This is a string matching problem where we can delete characters from the source string to match the target string, counting all distinct ways to do so.

State Variable

Let `dp[i][j]` be the number of ways to form the prefix of `T` of length `j` using the prefix of `S` of length `i`.

When Characters Match

If `S[i] == T[j]`, we can either use `S[i]` to match `T[j]` (`dp[i-1][j-1]`), OR we can ignore `S[i]` and rely on earlier characters (`dp[i-1][j]`).

When Characters Don't Match

If they don't match, we cannot use `S[i]`, so we MUST ignore it: `dp[i][j] = dp[i-1][j]`.

String S:Target T:

S \ T	""	r	a	b	b	i	t
""	1	0	0	0	0	0	0
r	1	0	0	0	0	0	0
a	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
i	1	0	0	0	0	0	0
t	1	0	0	0	0	0	0

Code Tracker

:::

1let dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

2for (let i = 0; i <= m; i++) dp[i][0] = 1;

3for (let i = 1; i <= m; i++) {

4 for (let j = 1; j <= n; j++) {

5 if (S[i-1] === T[j-1]) {

6 dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

7 } else {

8 dp[i][j] = dp[i-1][j];

9 }

10 }

11}

S \ T	""	r	a	b	b	i	t
""	1	0	0	0	0	0	0
r	1	0	0	0	0	0	0
a	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
i	1	0	0	0	0	0	0
t	1	0	0	0	0	0	0

S \ T	""	r	a	b	b	i	t
""	1	0	0	0	0	0	0
r	1	0	0	0	0	0	0
a	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
i	1	0	0	0	0	0	0
t	1	0	0	0	0	0	0

S \ T	""	r	a	b	b	i	t
""	1	0	0	0	0	0	0
r	1	0	0	0	0	0	0
a	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
i	1	0	0	0	0	0	0
t	1	0	0	0	0	0	0

S \ T	""	r	a	b	b	i	t
""	1	0	0	0	0	0	0
r	1	0	0	0	0	0	0
a	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
i	1	0	0	0	0	0	0
t	1	0	0	0	0	0	0

S \ T	""	r	a	b	b	i	t
""	1	0	0	0	0	0	0
r	1	0	0	0	0	0	0
a	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
i	1	0	0	0	0	0	0
t	1	0	0	0	0	0	0

S \ T	""	r	a	b	b	i	t
""	1	0	0	0	0	0	0
r	1	0	0	0	0	0	0
a	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
b	1	0	0	0	0	0	0
i	1	0	0	0	0	0	0
t	1	0	0	0	0	0	0