DSA Tracker

Visualize

Distinct Subsequences

dp[i][j] = dp[i][j-1] (skip s[j-1]) + dp[i-1][j-1] when s[j-1] closes a match on t[i-1]

time O(m * n)space O(m * n)

Build a table where dp[i][j] answers: how many ways does the first j characters of s spell out the first i characters of t? Every character of s has exactly one choice to make: get skipped, or get used. Skipping always carries forward whatever dp[i][j-1] already counted. Using it only makes sense when s[j-1] equals the next character t needs, t[i-1] — and when it does, every way of matching t[0..i-2] out of s[0..j-2] becomes a new way of matching t[0..i-1] out of s[0..j-1]. The two contributions never overlap, so they add.

Details

Animated on: s = "baba", t = "ba" — count the distinct ways to delete characters from s so what remains equals t.

Problem:Distinct SubsequencesHard

dp[i][j] = dp[i][j-1] (skip s[j-1]) + dp[i-1][j-1] when s[j-1] closes a match on t[i-1]

step 1 / 10

dp over t="ba" (rows) x s="baba" (cols) — dp[i][j] = ways s[0..j-1] forms t[0..i-1]

dp[0][j] = 1 for every j: the empty target "" is formed exactly one way from any prefix of s — by deleting everything.

Pseudocode
1FUNCTION numDistinct(s, t):
2  m <- LENGTH(s)
3  n <- LENGTH(t)
4  FOR j FROM 0 TO m: dp[0][j] <- 1
5  FOR i FROM 1 TO n:
6    FOR j FROM 1 TO m:
7      dp[i][j] <- dp[i][j-1]
8      IF s[j-1] = t[i-1]:
9        dp[i][j] <- dp[i][j] + dp[i-1][j-1]
10  RETURN dp[n][m]

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. dp[0][j] = 1 for every j: the empty target "" is formed exactly one way from any prefix of s — by deleting everything.
  2. s[0]='b' matches t[0]='b', so dp[1][1] can either skip this s and inherit dp[1][0]=null, or use it to close a match and inherit dp[0][0]=1: dp[1][1] = null + 1 = 1.
  3. s[1]='a' != t[0]='b', so it can only be skipped: dp[1][2] = dp[1][1] = 1.
  4. s[2]='b' matches t[0]='b', so dp[1][3] can either skip this s and inherit dp[1][2]=1, or use it to close a match and inherit dp[0][2]=1: dp[1][3] = 1 + 1 = 2.
  5. s[3]='a' != t[0]='b', so it can only be skipped: dp[1][4] = dp[1][3] = 2.
  6. s[0]='b' != t[1]='a', so it can only be skipped: dp[2][1] = dp[2][0] = 0.
  7. s[1]='a' matches t[1]='a', so dp[2][2] can either skip this s and inherit dp[2][1]=0, or use it to close a match and inherit dp[1][1]=1: dp[2][2] = 0 + 1 = 1.
  8. s[2]='b' != t[1]='a', so it can only be skipped: dp[2][3] = dp[2][2] = 1.
  9. s[3]='a' matches t[1]='a', so dp[2][4] can either skip this s and inherit dp[2][3]=1, or use it to close a match and inherit dp[1][3]=2: dp[2][4] = 1 + 2 = 3.
  10. dp[2][4] = 3 — s = "baba" contains t = "ba" as a subsequence in 3 distinct ways.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Distinct Subsequences in the editorAll Dynamic Programming problemsBack to roadmap