Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s which equals t.

• 1 ≤ s.length, t.length ≤ 1000
• s and t consist of English letters.

Examples

How to think about it

At each index of s, we need to decide what to do with the current character to build the target string t. We can model this as a tree of decisions:

1. Always Skip: We can choose to skip s[i]. We move i forward but keep j the same. This explores other occurrences of t[j] later in s.
2. Conditional Match: If s[i] == t[j], we can choose to use this matching character. We move both i and j forward.

1. Recursion / DFS

Using the logic above, we can write a pure recursive function dfs(i, j). We need robust base cases so our recursion can terminate correctly:

• If j == len(t): We have successfully matched all of string t. Return 1 (one valid way).
• If i == len(s): We ran out of characters in s but still need more for t. Return 0.

2. Dynamic Programming (Top-Down)

The recursive tree will visit the same (i, j) pairs repeatedly. We can memoize the results of these subproblems in a hash map dp[(i, j)]. If we see a state again, we return the cached value.

3. Dynamic Programming (Bottom-Up)

We can convert this to an iterative 2D DP table. The table dimension is (len(s) + 1) × (len(t) + 1).

Initialize the first column (where t is empty) to 1. Iterate backwards. The transitions are exactly the same as our recursive logic.

4. Space Optimized DP

Notice that in the 2D table approach, computing the current row dp[i] solely depends on the row immediately below it dp[i + 1]. We don't need to keep the entire M × N matrix in memory.

We can reduce the space complexity to O(N) by only maintaining a single 1D array of size N + 1. When building iteratively, we overwrite the previous row.