#115
Distinct Subsequences
Hard 2D DP counting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count how many distinct ways t appears as a subsequence of s.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: in how many ways does t appear as a subsequence of s?
Why this works: dp[j] = ways to build t's first j letters. A matching letter of s can extend dp[j-1] (loop j downward).
Example: s "rabbbit", t "rabbit"
choose which 2 of the 3 b's → 3 ways✦Hints open one at a time
dp[i][j] = ways to form the first j chars of t from the first i chars of s.
You can always skip s[i−1]. If it matches t[j−1], you can also use it.
↗Approach
dp[i][0] = 1 (empty t). Transition: dp[i][j] = dp[i−1][j] + (match ? dp[i−1][j−1] : 0). A 1D array with j going downwards works.
</>Solution (Java)
class Solution {
public int numDistinct(String s, String t) {
int m = t.length();
long[] dp = new long[m + 1]; // long to be safe with intermediate counts
dp[0] = 1;
for (int i = 0; i < s.length(); i++) {
for (int j = m; j >= 1; j--) { // downwards: s[i] used at most once
if (s.charAt(i) == t.charAt(j - 1)) dp[j] += dp[j - 1];
}
}
return (int) dp[m];
}
}!Common mistake
Looping j upwards in the 1D version, which reuses the same character of s twice.
Complexity
- Time: O(n·m).
- Space: O(m).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon