Distinct Subsequences
Count the ways t appears as a subsequence of s with a 2D DP table: every letter of s is skipped, or used when it matches the next letter of t.
Problem Understanding
Distinct Subsequences: given strings s and t, return how many distinct subsequences of s equal t. A subsequence keeps letters in order but may drop any of them; two subsequences are different if they use different positions of s.
Example: s = "rabbbit", t = "rabbit" returns 3: drop any one of the three b's. s = "babgbag", t = "bag" returns 5.
The Intuition: Skip It or Use It
Walk through s one letter at a time. Each letter makes a choice:
- Skip it: the ways to spell
t[..j]are the ways you already had without it,dp[i - 1][j]. - Use it, only if it equals
t[j - 1]: it finishest[..j], so add every way of spellingt[..j - 1]before it,dp[i - 1][j - 1].
The two choices never overlap (one uses position i - 1, the other does not), so their counts simply add. It is the same two-string table as Longest Common Subsequence and Interleaving String, with counts that add instead of a max or a true/false. Regular Expression Matching runs the same grid with pattern rules. The skip-or-take choice is the core of dynamic programming on sequences.
Interactive Walkthrough
t runs across the top and s down the left. The live cell is solid and the cells it adds are tinted: above for skip, diagonal for use. Try Choose 3 of 8 to see the table build binomial coefficients.
Dry Run Table
Input: s = "babgbag" (down), t = "bag" (across)
| ∅ | b | a | g | |
|---|---|---|---|---|
| ∅ | 1 | 0 | 0 | 0 |
| b | 1 | 1 | 0 | 0 |
| a | 1 | 1 | 1 | 0 |
| b | 1 | 2 | 1 | 0 |
| g | 1 | 2 | 1 | 1 |
| b | 1 | 3 | 1 | 1 |
| a | 1 | 3 | 4 | 1 |
| g | 1 | 3 | 4 | 5 |
- Row 6 (
a), columna: skip gives 1, use gives the 3 ways to spell"b"before it: 4. - Row 7 (
g), columng: skip gives 1, use gives the 4 ways to spell"ba": 5.
Answer: 5.
The Solution Template
A full (m + 1) × (n + 1) table. Intermediate counts can exceed the final answer, so C++ and C use unsigned long long (wrap-around is defined there, and the answer is guaranteed to fit in 32 bits).
Distinct Subsequences Code
1var numDistinct = function(s, t) {2 const m = s.length, n = t.length;3 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));4 for (let i = 0; i <= m; i++) dp[i][0] = 1;5 for (let i = 1; i <= m; i++) {6 for (let j = 1; j <= n; j++) {7 dp[i][j] = dp[i - 1][j];8 if (s[i - 1] === t[j - 1]) dp[i][j] += dp[i - 1][j - 1];9 }10 }11 return dp[m][n];12};
Edge Cases & Common Mistakes
- t longer than s: the answer is 0; the table handles it without a special case.
- Forgetting column 0: if
dp[i][0]stays 0, every count stays 0. - Overflow: intermediate cells can be far bigger than the final answer. Use a 64-bit unsigned type in C and C++, where signed overflow is undefined.
- One-row version updated left to right:
dp[j - 1]is already overwritten with the new row; loopjfromndown to 1. - Counting distinct strings instead of positions: the problem counts index choices, so
"aaaa"contains"aa"6 ways, not 1.
Summary
Set dp[i][0] = 1. Each cell is dp[i - 1][j] (skip s[i - 1]), plus dp[i - 1][j - 1] when s[i - 1] equals t[j - 1] (use it). Return dp[m][n]. O(m · n) time, and O(n) space with one row updated right to left.
More practice: DSA interview questions with answers · patterns cheat sheet