Distinct subsequences
HardMatch or skip the character of s
Problem
Count how many distinct subsequences of s equal t.
Count how many ways t appears as a subsequence, adding matches letter by letter.
The idea
When the characters agree you may either use s[i] to match t[j] or skip it, so the counts add. When they differ, only skipping is possible. The base case is that an empty t is matched exactly one way.
The trick
- Matching: dp[i-1][j-1] + dp[i-1][j]; mismatching: dp[i-1][j].
- Empty t has exactly one matching — the empty subsequence.
- Counts grow fast; use 64-bit or take a modulus.
·
∅
A
C
∅
0
0
0
A
0
0
0
B
0
0
0
C
0
0
0
Step 1 of 8. LCS grid for "ABC" and "AC". Match → diagonal + 1, else the best of up/left.
1/8
Optimal
timeO(n·m)spaceO(n·m)
Match extends the diagonal.
1for (let i = 1; i <= n; i++)2 for (let j = 1; j <= m; j++)3 dp[i][j] = a[i-1] === b[j-1]4 ? dp[i-1][j-1] + 15 : Math.max(dp[i-1][j], dp[i][j-1]);Input
- grid
- 5 × 4
Memory
- at
- —
- cells marked
- 0
Output
- LCS
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "rabbbit", t = "rabbit"
- Output:
- 3
- Explanation:
- 3 ways to pick 'rabbit' from the b's.
Example 2
- Input:
- s = "babgbag", t = "bag"
- Output:
- 5
- Explanation:
- 5 different subsequences spell 'bag'.
Example 3
- Input:
- s = "abc", t = "abc"
- Output:
- 1
- Explanation:
- Exactly one way.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.