Distinct Subsequences
Distinct Subsequences: count how many subsequences of s equal t.
- 1 <= s.length, t.length <= 1000
- s and t consist of English letters.
Intuition
Distinct subsequences counts how many subsequences of s equal t. Generating all 2ⁿ subsequences of s and comparing is hopeless, so the counting must be structured.
Work through s one character at a time, tracking how many ways each prefix of t has been formed so far. When you meet a character of s, it either contributes or it does not:
- If s[i] equals t[j−1], every way of having already formed t[:j−1] becomes a new way of forming t[:j].
So the count for t[:j] gains the count for t[:j−1]. If the characters differ, that position of s is simply skipped and nothing changes.
Let dp[j] be the number of ways to form the first j characters of t using the part of s processed so far. Initialise dp[0] = 1, since the empty target is formed exactly one way — by choosing nothing — and every other entry to 0.
The subtlety is the update direction. Because dp[j] reads dp[j−1], and both refer to counts from before this character of s, you must iterate j from high to low. Going forward would let dp[j−1] already include the current character, and it would be counted twice — as if one s character could fill two positions of t.
That backward sweep is the same guard used in the 0/1 knapsack rolling array, and for the same reason.
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
Before reading on: price up what counting everything costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(|s| * |t|) time and O(|t|) space.
Track counts per target prefix
dp[j] is the number of ways the processed part of s forms t[:j]. One dimension suffices because the source position is implicit in how far the outer loop has advanced.
Initialise the empty target to one
dp[0] = 1: the empty string is formed exactly one way, by selecting no characters. Every other entry starts at 0. This base case is what every later count ultimately multiplies out from.
Add the shorter-prefix count on a match
When s[i] == t[j-1], do dp[j] += dp[j-1]. Every existing way of building t[:j-1] extends to t[:j] using this character — and the old dp[j] is kept, since not using this character is also valid.
Iterate j backwards
Sweep j from len(t) down to 1. Forward iteration would let dp[j-1] already include the current character, letting one s character fill two target positions and inflating the count — the same hazard as the 0/1 knapsack rolling array.
Skip non-matching characters
If the characters differ, no update happens at all — that position of s simply contributes nothing to this target position. The 'skip' branch needs no code because the counts already carry forward unchanged.
Watch the result size
The count can grow very large; LeetCode guarantees it fits in a signed 32-bit integer, but intermediate values in other formulations may not. Use 64-bit arithmetic if adapting this outside the stated constraints.
Cost of the sweep
For each of the n characters of s the inner loop runs m times, giving O(n·m) time and O(m) space with the rolling array — down from O(n·m) space for the full two-dimensional table.
Solution & live demo
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.