Distinct Subsequences

Examples

Input: s = "rabbbit", t = "rabbit"
Output: 3

There are 3 ways to delete two of the three b's from s to spell out rabbit.

Input: s = "babgbag", t = "bag"
Output: 5

Constraints

• 1 <= s.length, t.length <= 1000

• Both strings contain only English letters

Approach

Build a table where cell (i, j) means: "using only the first i characters of s, how many distinct ways are there to spell out the first j characters of t?"

The i-th character of s can always be skipped (deleted), which alone contributes as many ways as (i-1, j) already found. On top of that, if the i-th character of s happens to equal the j-th character of t, it can also be used to match that character, contributing however many ways (i-1, j-1) found. Add both possibilities together — they're two genuinely different sets of deletions, so they don't overlap.

The base case: matching an empty t (column 0) is always possible in exactly one way for any prefix of s — delete everything.

Solutions

Brute Force — Recursion

Walk s and t from the front together. At each step, always try skipping the current character of s; additionally, if it matches the current character of t, try consuming both. Sum the ways found down each branch.

function numDistinct(s, t) {
  function solve(i, j) {
    if (j === t.length) return 1;
    if (i === s.length) return 0;

    let ways = solve(i + 1, j); // skip s[i]
    if (s[i] === t[j]) {
      ways += solve(i + 1, j + 1); // use s[i] to match t[j]
    }
    return ways;
  }

  return solve(0, 0);
}

Time: O(2^m), where m is the length of s · Space: O(m) — recursion depth

Optimal — Bottom-Up 2D Table

Build a table over (prefix length of s, prefix length of t), seeding column 0 with 1 (an empty t is always matched exactly one way), then filling every other cell as 'skip' plus, when characters match, 'use.'

function numDistinct(s, t) {
  const m = s.length;
  const n = t.length;
  const table = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) {
    table[i][0] = 1; // empty t is always formed exactly one way: delete everything
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      table[i][j] = table[i - 1][j]; // skip s[i - 1]
      if (s[i - 1] === t[j - 1]) {
        table[i][j] += table[i - 1][j - 1]; // also use s[i - 1] to match t[j - 1]
      }
    }
  }

  return table[m][n];
}

Time: O(m * n) · Space: O(m * n)