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.

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 to dynamic programming.

Key Constraints:

Intuition

We can express the answer recursively by starting at the end of both strings and working backwards. At each step we ask one question: how many ways can we 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]. The answer is then 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 recursion carries call-stack overhead and risks a stack overflow when s is long. The next approach fills the same table iteratively, bottom-up, removing 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, by deleting everything), and dp[0][j] = 0 for j > 0 (no way to form a non-empty string from an empty string).

The sum does not double-count. Each subsequence that forms t[0..j-1] either includes the character at position i-1 of s or it does not, and those two sets are disjoint. The match term dp[i-1][j-1] counts the subsequences that use s[i-1] as the final matched character, and the skip term dp[i-1][j] counts those that do not use s[i-1] at all. Adding them covers every case exactly once.

Algorithm

Example Walkthrough

Code

Each row of the table depends only on the row directly above it. The next approach exploits that to compress the table into a single row, cutting 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.

The iteration order matters. 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 the diagonal dependency needs the old dp[j-1] from the previous row. Iterating j from right to left avoids this: when we update dp[j], the value at dp[j-1] still holds the previous row's value.

Algorithm

Example Walkthrough

Code