115. Distinct Subsequences

Count how many distinct ways you can delete characters from s to produce t. A 2D DP table where dp[i][j] counts ways s[i:] can form t[j:] — at each matching pair you either skip s[i] or use both characters.

● Hard2D DPString DPSubsequenceTypeScript

PROBLEM Count distinct subsequence occurrences

Given strings s and t, return the number of distinct ways to delete characters from s so that the remaining characters equal t (in order). Each position in s can be used at most once.

Worked example: s = "rabbbit", t = "rabbit". The extra 'b' in scan be the "dropped" one in three distinct positions, so the answer is 3.

Another: s = "babgbag", t = "bag" → 5. There are five distinct index-triples in sthat spell "bag".

KEY IDEA At a match, choose: skip s[i] or consume both

Insight → define dp[i][j] = number of ways s[i:] can form t[j:]. When s[i] === t[j] you have two independent choices: skip s[i] and stay on t[j](the "skip-s" branch, worth dp[i+1][j]ways), or match them both and advance (the "take-both" branch, worth dp[i+1][j+1] ways). Add the two. When characters differ you can only skip s[i]. The answer is dp[0][0].

RECURRENCE Bottom-up recurrence

0 · Define the subproblem. dp[i][j] = ways s[i..m-1] can form t[j..n-1]. Suffixes, not prefixes — this keeps the recurrence additive.
1 · Base cases. dp[i][n] = 1 for all i: an empty target is trivially matched. dp[m][j] = 0 for j < n: no source left, target still non-empty = impossible.
2 · Skip-s branch. We can always discard s[i] and try to form the same t[j:] from the rest: dp[i][j] += dp[i+1][j].
3 · Take-both branch (match only). If s[i] === t[j], also add dp[i+1][j+1]: consume both characters and count the ways the remaining suffixes align.
4 · Fill order. Loop i from m-1 down to 0, inner loop j from n-1 down to 0. Each cell needs dp[i+1][...], which is already filled.
5 · Answer. Return dp[0][0].

Classic confusion → many learners write dp[i][j]as "prefixes" (s[0..i] forms t[0..j]) and recur backward — that's equivalent, but the suffix formulation makes the take-both branch feel more natural: dp[i+1][j+1] rather than dp[i-1][j-1]. Either direction is valid; be consistent and never mix the two.

COST Complexity & space reduction

Brute force (all subseqs)

O(2ⁿ)

Generate every subsequence of s and compare to t.

2D DP

O(m·n)

O(m·n) time; O(m·n) space — or O(n) with rolling array.

Space reduction

Because row i only ever reads row i+1, you can keep just two 1-D arrays (or one array iterated right-to-left) and cut space from O(m·n) to O(n). Iterate jfrom high to low so you don't overwrite a value you still need.

Pattern transfer → the "skip or take-both" two-branch recurrence appears in Edit Distance (three branches: insert/delete/replace), Longest Common Subsequence (same shape, max instead of sum), Wildcard Matching, and Regular Expression Matching. Whenever you see "how many ways can A embed into B?" reach for this 2D suffix-DP template.

RUN IT Fill dp[i][j]: ways s[i:] forms t[j:]

s =t =

step 0 / 85

STARTInitialize dp[i][n] = 1 for all i (empty t matched 1 way), and dp[m][j] = 0 for j < n (empty s, non-empty t = 0 ways).

1▶function numDistinct(s: string, t: string): number {
2▶  const m = s.length, n = t.length;
3  // dp[i][j] = number of ways s[i..m-1] can form t[j..n-1]
4▶  const dp: number[][] = Array.from({ length: m + 1 }, () =>
5▶    new Array(n + 1).fill(0)
6▶  );
7  // Base case: empty t is matched by any suffix of s exactly 1 way
8▶  for (let i = 0; i <= m; i++) dp[i][n] = 1;
9 
10  // Fill bottom-up: iterate i right-to-left, j right-to-left
11  for (let i = m - 1; i >= 0; i--) {
12    for (let j = n - 1; j >= 0; j--) {
13      // skip s[i]: always allowed — move to dp[i+1][j]
14      dp[i][j] = dp[i + 1][j];
15      // take-both: only when characters match
16      if (s[i] === t[j]) dp[i][j] += dp[i + 1][j + 1];
17    }
18  }
19  return dp[0][0];
20}

j→

State
m: 7
n: 6
base: dp[i][6] = 1 for all i

current cellsource cellschosen / written

slowfast

TYPESCRIPT The solution, annotated

numDistinct.ts
function numDistinct(s: string, t: string): number {
  const m = s.length, n = t.length;
  // dp[i][j] = number of ways s[i..m-1] can form t[j..n-1]
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );
  // Base case: empty t is matched by any suffix of s exactly 1 way
  for (let i = 0; i <= m; i++) dp[i][n] = 1;

  // Fill bottom-up: iterate i right-to-left, j right-to-left
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      // skip s[i]: always allowed — move to dp[i+1][j]
      dp[i][j] = dp[i + 1][j];
      // take-both: only when characters match
      if (s[i] === t[j]) dp[i][j] += dp[i + 1][j + 1];
    }
  }
  return dp[0][0];
}

Reading it block by block

Lines 2–5 — allocate the table. We build an (m+1) × (n+1)grid initialised to zero. The extra row and column hold the base cases; their indices correspond to "nothing left of s" and "nothing left of t" respectively.

Line 7 — base case: empty target. Setting dp[i][n] = 1 for every isays: "once t is exhausted, there is exactly one way to match — stop deleting." The row dp[m][j] for j < n remains zero: s is exhausted but t is not; impossible.

Lines 10–16 — bottom-up fill. We iterate i from m-1 down to 0 (right-to-left over s) and j from n-1 down to 0 (right-to-left over t). Each cell needs dp[i+1][...], which is already computed.

Line 13 — skip-s branch. dp[i][j] = dp[i+1][j] counts all the ways we can form t[j:] without using s[i]at all. This is always valid — we're just ignoring one character of s.

Lines 14–15 — take-both branch. Only when s[i] === t[j] do we also add dp[i+1][j+1]: we consume s[i] as the match for t[j] and recurse on the remaining suffixes. The two branches are independent so we add (not take-max).

Line 18 — return dp[0][0].The full problem is "ways s[0:] forms t[0:]" — exactly the top-left cell.

Complexity → O(m·n) time (two nested loops, constant work per cell) and O(m·n) space for the table. A rolling-array optimisation reduces space to O(n) by keeping only one row at a time — iterate j right-to-left to avoid overwriting the dp[i+1][j+1] value before it's read.

INTERVIEWFollow-ups they'll ask

"Reduce to O(n) space?" Replace the 2D array with a single 1-D array and iterate j from n-1 down to 0 so you read dp[j+1] before overwriting dp[j].
"Return one actual deletion sequence, not just the count?" Store parent pointers in a separate table and backtrack from dp[0][0], choosing the skip-s path or take-both path based on which branch contributed.
"What if s and t can have wildcards?"Wildcard Matching (LC 44) and Regular Expression Matching (LC 10) extend this same DP frame by adding a third branch for the wildcard/'.' match.
"What's the brute-force?" Enumerate all 2ⁿ subsequences of s and count those equal to t. DP memoises the repeated suffix sub-problems that make recursion exponential.
"Overflow?" Counts can be astronomically large (the problem guarantees the answer fits in a 32-bit int, but in general use BigInt or arbitrary precision if the constraints are looser).

OPTIMAL 2D DP

numDistinct.ts
function numDistinct(s: string, t: string): number {
  const m = s.length, n = t.length;
  // dp[i][j] = number of ways s[i..m-1] can form t[j..n-1]
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );
  // Base case: empty t is matched by any suffix of s exactly 1 way
  for (let i = 0; i <= m; i++) dp[i][n] = 1;

  // Fill bottom-up: iterate i right-to-left, j right-to-left
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      // skip s[i]: always allowed — move to dp[i+1][j]
      dp[i][j] = dp[i + 1][j];
      // take-both: only when characters match
      if (s[i] === t[j]) dp[i][j] += dp[i + 1][j + 1];
    }
  }
  return dp[0][0];
}

ALT 1 Top-down recursion + memo

O(m·n) time, O(m·n) space

Recurse on the suffixes (i, j)and cache each result — the most direct translation of the "skip or take-both" recurrence.

approach-2.ts
function numDistinct(s: string, t: string): number {
  const m = s.length, n = t.length;
  // memo[i][j] = ways s[i:] can form t[j:]; -1 = not yet computed
  const memo: number[][] = Array.from({ length: m + 1 }, () =>
    new Array<number>(n + 1).fill(-1)
  );

  function solve(i: number, j: number): number {
    if (j === n) return 1;       // empty target: one way (delete the rest)
    if (i === m) return 0;       // source exhausted, target left: impossible
    if (memo[i][j] !== -1) return memo[i][j];

    let ways = solve(i + 1, j);  // skip s[i] — always allowed
    if (s[i] === t[j]) {
      ways += solve(i + 1, j + 1); // take both — only on a match
    }
    memo[i][j] = ways;
    return ways;
  }

  return solve(0, 0);
}

Note → Same O(m·n) states as the bottom-up table, just filled lazily. Recursion depth is O(m + n); for very long s the explicit table avoids stack-overflow risk.

ALT 2 1D rolling-array DP

O(m·n) time, O(n) space

Collapse the table to a single row over t, updating it right-to-left as each character of s is consumed.

approach-3.ts
function numDistinct(s: string, t: string): number {
  const m = s.length, n = t.length;
  // dp[j] = ways the processed prefix of s can form t[0:j]
  const dp: number[] = new Array<number>(n + 1).fill(0);
  dp[0] = 1; // empty target is matched exactly one way

  for (let i = 0; i < m; i++) {
    // iterate j right-to-left so dp[j-1] still holds the PREVIOUS
    // row's value (s[i] used at most once per target position)
    for (let j = n; j >= 1; j--) {
      if (s[i] === t[j - 1]) {
        dp[j] += dp[j - 1];
      }
    }
  }

  return dp[n];
}

Note → The right-to-left inner loop is essential: it guarantees dp[j - 1] reflects the row before s[i] was added, so each source character contributes to a given target position at most once. Left-to-right would let one s[i] be reused and overcount.

ALT 3 Brute force — enumerate every subsequence of s

O(2ⁿ · m) time · O(n) space

Recursively decide to keep or drop each character of s, and count the resulting subsequences that exactly equal t— the literal definition of the answer.

approach-4.ts
function numDistinct(s: string, t: string): number {
  const m = s.length;
  let count = 0;

  // At index i of s, having built 'built' so far, branch on keep vs skip.
  function recurse(i: number, built: string): void {
    if (built.length > t.length) return; // can never shrink back
    if (i === m) {
      if (built === t) count++;          // a subsequence that matches t
      return;
    }
    recurse(i + 1, built + s[i]); // keep s[i]
    recurse(i + 1, built);        // drop s[i]
  }

  recurse(0, '');
  return count;
}

Note → There are 2ⁿ subsequences of s and comparing each to t costs O(m), so this blows up exponentially. The DP memoises the overlapping (i, j) suffix sub-problems this recursion revisits, collapsing it to O(m·n).

MNEMONIC The one-liner

"Skip s or take both — always add dp[i+1][j]; on a match also add dp[i+1][j+1]. dp[0][0] is your answer."

TRIGGERS When you see _ → reach for _

"how many distinct ways" + subsequence	2D suffix DP, add two branches
count subsequence occurrences of t in s	dp[i][j] = ways s[i:] forms t[j:]
"delete characters from s to get t"	dp[i+1][j] + (match ? dp[i+1][j+1] : 0)
answer too large for brute force	O(m·n) DP memoises suffix sub-problems

SKELETON The reusable shape

skeleton.ts
function numDistinct(s: string, t: string): number {
  const m = s.length, n = t.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );
  for (let i = 0; i <= m; i++) dp[i][n] = 1; // base: empty t
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      dp[i][j] = dp[i + 1][j];               // skip s[i]
      if (s[i] === t[j]) dp[i][j] += dp[i + 1][j + 1]; // take both
    }
  }
  return dp[0][0];
}

FLASHCARDS Tap to flip

What does dp[i][j] mean in this problem?

The number of ways s[i..m-1] can form t[j..n-1] as a subsequence.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the value of dp[i][n] (the rightmost column) for every valid i?

QUESTION 02

Why do we ADD dp[i+1][j] and dp[i+1][j+1] on a character match instead of taking the max?

QUESTION 03

For s = "rabbbit", t = "rabbit", what does the algorithm return?

QUESTION 04

Which fill order is correct for the bottom-up DP?

QUESTION 05

What is the time and space complexity of the standard 2D DP solution?

QUESTION 06

If s[i] !== t[j], what is dp[i][j]?

QUESTION 07

How does reducing to O(n) space work? Which direction must the inner j-loop run?

QUESTION 08

#115 · Distinct Subsequences2D DP counting ways s forms t: on a character match, add both the "use s[i]" branch (dp[i+1][j+1]) and the "skip s[i]" branch (dp[i+1][j]); on a mismatch, only skip. Fill from the bottom right.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM Count distinct subsequence occurrences

KEY IDEA At a match, choose: skip s[i] or consume both

RECURRENCE Bottom-up recurrence

COST Complexity & space reduction

Space reduction

RUN IT Fill dp[i][j]: ways s[i:] forms t[j:]

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL 2D DP

ALT 1 Top-down recursion + memo

ALT 2 1D rolling-array DP

ALT 3 Brute force — enumerate every subsequence of s

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _