Distinct subsequences

Hard TimeO(n·m) SpaceO(m)

A subsequence of s keeps its order but may skip characters, and two count as different when they use different positions, even when the text is identical. Given s and t, return how many distinct subsequences of s equal t. Characters are never reordered, and an empty t is matched exactly once, by taking nothing.

Examples

Example 1

Input
s = "rabbbit"t = "rabbit"
Output
3
Three bs in s and two needed, and there are 3 ways to choose which two.

Example 2

Input
s = "abc"t = ""
Output
1
The empty string is matched exactly once, by taking nothing at all.

The Code

function numDistinct(s, t) {
  const dp = new Array(t.length + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= s.length; i++) {
    for (let j = t.length; j >= 1; j--) {
      if (s[i - 1] === t[j - 1]) {
        dp[j] = dp[j] + dp[j - 1];
      }
    }
  }
  return dp[t.length];
}
numDistinct("rabbbit", "rabbit");
Done

The first 14 calls, of 58. This one does not fit on a page.

Step through numDistinct("rabbbit", "rabbit") call by call

More like this

All dynamic programming examples (20) →