Intuition
Enumerating all subsequences of s produces 2^n candidates. At each source character, a valid construction either skips it or, when it matches the next target character, uses it. The number of ways depends only on the current source and target positions. A one-dimensional DP can aggregate these choices while scanning the source once.
Counting ways to obtain one sequence by deleting elements from another suggests subsequence DP. When each source item may be used once, reverse the compressed DP update direction.
Approach
Let target-prefix counts summarize earlier choices
Set dp[j] to the number of ways the processed source prefix forms the first j target characters. Initialize dp[0] = 1 because every source prefix contains the empty target once.
Update a match by extending shorter subsequences
For each source character, if it equals t[j - 1], add dp[j - 1] to dp[j]. Every prior way to form the shorter target now gains a distinct choice using the current source position.
Traverse target positions backward
Update j from the target length down to one. Backward order ensures dp[j - 1] still represents choices from before the current source character, preventing that character from being reused twice.
Solution
Common pitfalls
Updating target positions forward
for j in range(1, len(t) + 1):
for j in range(len(t), 0, -1):
Forward updates can reuse the current source character multiple times.
Forgetting the empty-target base case
dp = [0] * (len(t) + 1)
dp = [1] + [0] * len(t)
The empty target has one construction before any source characters are processed.
Replacing instead of accumulating
dp[j] = dp[j - 1]
dp[j] += dp[j - 1]
Ways that skip the current source character remain valid alongside ways that use it.
Edge cases
Return one because deleting every source character forms it in exactly one way.
No count can reach the target length, so the result remains zero.
Each matching source index extends earlier counts separately, preserving distinct index choices.