Distinct Subsequences
Problem Statement
Given two strings s and t, return the number of distinct subsequences of s that equal t. A subsequence is formed by deleting zero or more characters without changing the relative order of the remaining characters.
Input
Two strings s and t.
Output
An integer: the number of subsequences of s that exactly form t.
Constraints
- •
1 <= s.length, t.length <= 1000 - •
s and t consist of English letters. - •
The answer fits in a signed 32-bit integer.
Examples
Example 1
s = rabbbit, t = rabbit
3Example 2
s = babgbag, t = bag
5Example 3
s = abc, t = abc
1Learning Objectives
- Model subsequence counting as a DP over two prefixes, one from the source and one from the target.
- Separate the two choices for each source character: skip it, or use it when it matches the next target character.
- Anchor counting DP with the empty target base case **dp[i][0] = 1**.
- Compress the table to one row by iterating target positions from right to left.
Intuition
Think of scanning s from left to right while trying to build t. When the current character of s does not match the current character of t, it cannot help that target position, so the only choice is to skip it.
When the characters do match, two disjoint groups of subsequences appear. Some skip this character of s and were already counted before. Others use this character as the final character of the current target prefix, so everything before it must have formed the previous target prefix. Adding those two groups counts every valid subsequence exactly once.
Common mistakes
- ×Using substring matching instead of subsequence matching; characters in **s** may be skipped but order must stay fixed.
- ×Forgetting that the empty target has one match in every prefix of **s**: choose nothing.
- ×Updating a 1D table from left to right, which lets the same source character satisfy multiple target positions.
- ×Using **dp[i - 1][j - 1]** alone on a match and accidentally dropping the skip-this-character choices.
- ×Returning 0 when **t** is empty; the correct count is 1.
State Definition
Let dp[i][j] be the number of subsequences of the prefix s[0..i) that equal the prefix t[0..j). The answer is dp[m][n], where m = s.length and n = t.length.
State Transition
Base cases: dp[i][0] = 1 for every i, because the empty target is formed by deleting everything. Also dp[0][j] = 0 for every positive j, because an empty source cannot form a non-empty target.
For i > 0 and j > 0, first carry over the subsequences that skip s[i - 1]: dp[i - 1][j]. If s[i - 1] == t[j - 1], we can also use that source character to finish the target prefix, adding dp[i - 1][j - 1].
So the recurrence is dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] on a character match, otherwise dp[i][j] = dp[i - 1][j].
Solutions
Solution 1: Bottom-up 2D table
Build the prefix table directly. Each row adds one more character from s, and each column asks how many ways that source prefix can form a target prefix.
Step-by-step
- Create a table with m + 1 rows and n + 1 columns.
- Fill column 0 with 1 because every source prefix forms the empty target once.
- For every source index i and target index j, copy dp[i - 1][j] for the skip case.
- If the current characters match, add dp[i - 1][j - 1] for the use case.
- Return dp[m][n].
O(m · n)
O(m · n)
Every pair of source and target prefix lengths is computed once.
Java implementation
Solution 2: Space-optimized 1D table
Use this after explaining the 2D recurrence when the interviewer asks for memory optimisation or when t is much shorter than s.
A row only depends on the previous row. Keep one array where dp[j] means the count for target prefix length j after processing the current source prefix. Iterate j descending so dp[j - 1] still belongs to the previous row.
Step-by-step
- Initialise dp[0] = 1 for the empty target.
- Scan each character of s from left to right.
- For target positions from n down to 1, add dp[j - 1] into dp[j] when the characters match.
- Descending order preserves the previous-row value needed by the use case.
- Return dp[n] after all source characters are processed.
O(m · n)
O(n)
Only the previous target-prefix counts are kept.
Java implementation
Dry Run
Sample input
s = rabbbit, t = rabbit. The 1D row is shown after each processed source character for target prefixes empty, r, ra, rab, rabb, rabbi, rabbit.
| i | source char | processed prefix | dp row | note |
|---|---|---|---|---|
| 0 | none | empty | [1,0,0,0,0,0,0] | Empty target has one match before scanning **s**. |
| 1 | r | r | [1,1,0,0,0,0,0] | The first character can form target prefix r. |
| 2 | a | ra | [1,1,1,0,0,0,0] | The prefix ra is now formed once. |
| 3 | b | rab | [1,1,1,1,0,0,0] | The first **b** can finish rab. |
| 4 | b | rabb | [1,1,1,2,1,0,0] | Two ways now form rab, and one way forms rabb. |
| 5 | b | rabbb | [1,1,1,3,3,0,0] | Any two of the three **b** positions can serve the two target **b** positions. |
| 6 | i | rabbbi | [1,1,1,3,3,3,0] | Each rabb match can extend to rabbi. |
| 7 | t | rabbbit | [1,1,1,3,3,3,3] | Each rabbi match extends to the full target. |
The final count for the full target is 3, matching the three possible choices of which middle b to skip.
Complexity Analysis
Both solutions use the same O(m · n) recurrence. The 1D form is the interview-ready optimisation once the 2D table is understood.
Bottom-up 2D table
O(m · n)
O(m · n)
Every pair of source and target prefix lengths is computed once.
Space-optimized 1D table
O(m · n)
O(n)
Only the previous target-prefix counts are kept.
Interview Tips
Derive the recurrence from the current source character: skip it always, and use it only when it matches the current target character. Say the empty target base case out loud, because it is the most common missing row or column. If you present the 1D optimisation, emphasise descending target iteration to avoid reusing one source character twice.
Likely follow-ups
- How would you return the count modulo a large prime if the answer did not fit in 32 bits?
- How would you reconstruct one actual subsequence of **s** that forms **t**?
- What changes if **s** is streamed one character at a time?
- How would you count distinct subsequences for many target strings against the same source?
Similar Problems
Key Takeaways
- Two-string counting DP usually tracks how many ways one prefix can form another prefix.
- A match creates two disjoint groups: skip the source character or use it.
- The empty target base case contributes one way for every source prefix.
- 1D compression requires descending target iteration.