We need to count how many ways we can delete characters from s to produce t. The order of characters must be preserved, so we are looking for subsequences, not substrings.

Consider a simpler example: s = "aab" and t = "ab". We can pick the first 'a' paired with 'b', or the second 'a' paired with 'b'. That gives us 2 distinct subsequences. The word "distinct" here means two subsequences are different if they use characters at different positions in s, even if the resulting strings look the same.

The key observation is that this problem has optimal substructure. When we look at the last character of both strings, we face a choice: if s[i] == t[j], we can either use this character match (and solve the smaller problem for s[0..i-1] and t[0..j-1]) or skip it in s (and solve for s[0..i-1] and t[0..j]). The total count is the sum of both choices. This branching structure with overlapping subproblems points directly to dynamic programming.

Key Constraints:

Intuition

The most natural way to think about this problem is recursively. Start at the end of both strings and work backwards. At each step, we ask: "How many ways can I form t[0..j-1] from s[0..i-1]?"

If s[i-1] == t[j-1], we have two options. We can use this character match, which means we now need to form t[0..j-2] from s[0..i-2]. Or we can skip s[i-1] and try to form t[0..j-1] from s[0..i-2]. The total is the sum of both choices.

If s[i-1] != t[j-1], we have no choice but to skip s[i-1]. So the answer is just the number of ways to form t[0..j-1] from s[0..i-2].

The base cases are straightforward. If j == 0 (we have matched all of t), there is exactly one way: we matched everything. If i == 0 but j > 0 (we ran out of characters in s but still have characters left in t), there are zero ways.

Without memoization, this recursion would revisit the same (i, j) pairs many times, leading to exponential time. But there are only m * n unique subproblems, so caching results brings it down to O(m * n).

Algorithm

Example Walkthrough

Code

The recursive approach works but carries recursion stack overhead. What if we filled the table systematically bottom-up, eliminating recursion entirely?

Intuition

Instead of solving subproblems on demand, we fill a 2D table systematically. Define dp[i][j] as the number of distinct subsequences of s[0..i-1] that equal t[0..j-1].

The recurrence is the same as before:

The base cases: dp[i][0] = 1 for all i (one way to form an empty string: delete everything), and dp[0][j] = 0 for j > 0 (no way to form a non-empty string from an empty string).

Algorithm

Example Walkthrough

Code

The 2D table works, but each row only depends on the row directly above it. Can we compress to a single row and cut space from O(m * n) to O(n)?

Intuition

Look at the recurrence again: dp[i][j] depends on dp[i-1][j] (directly above) and dp[i-1][j-1] (diagonally above-left). Both values come from the previous row only. So instead of a full 2D table, we can use a single 1D array of size n+1 and update it for each character in s.

There is one catch. If we iterate j from left to right, by the time we compute dp[j], we have already overwritten dp[j-1] with the current row's value. But we need the old dp[j-1] (from the previous row) for the diagonal dependency. The fix is simple: iterate j from right to left. That way, when we update dp[j], the value at dp[j-1] still holds the previous row's value, which is exactly what we need.

Algorithm

Example Walkthrough

Code