Distinct Subsequences
Count distinct subsequences of s that equal t — 2D DP over prefix counts.
3 min read
dp string
Problem#
Return the number of distinct subsequences of s that equal t.
Examples#
s = "rabbbit", t = "rabbit"→3s = "babgbag", t = "bag"→5
Constraints#
1 <= n, m <= 1000.
Approach#
dp[j] = number of ways t[:j] appears in the processed prefix of s. For each s[i], update j from m down to 1: if s[i] == t[j-1], dp[j] += dp[j-1].
Solution#
class Solution {public: int numDistinct(string s, string t) { int n = s.size(), m = t.size(); vector<unsigned long long> dp(m + 1, 0); dp[0] = 1; for (int i = 0; i < n; ++i) { for (int j = m; j >= 1; --j) { if (s[i] == t[j - 1]) dp[j] += dp[j - 1]; } } return (int)dp[m]; }};func numDistinct(s string, t string) int { n, m := len(s), len(t) dp := make([]uint64, m+1) dp[0] = 1 for i := 0; i < n; i++ { for j := m; j >= 1; j-- { if s[i] == t[j-1] { dp[j] += dp[j-1] } } } return int(dp[m])}class Solution: def numDistinct(self, s: str, t: str) -> int: n, m = len(s), len(t) dp = [0] * (m + 1) dp[0] = 1 for i in range(n): for j in range(m, 0, -1): if s[i] == t[j - 1]: dp[j] += dp[j - 1] return dp[m]var numDistinct = function(s, t) { const n = s.length, m = t.length; const dp = new Array(m + 1).fill(0); dp[0] = 1; for (let i = 0; i < n; i++) { for (let j = m; j >= 1; j--) { if (s[i] === t[j - 1]) dp[j] += dp[j - 1]; } } return dp[m];};class Solution { public int numDistinct(String s, String t) { int n = s.length(), m = t.length(); long[] dp = new long[m + 1]; dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = m; j >= 1; j--) { if (s.charAt(i) == t.charAt(j - 1)) dp[j] += dp[j - 1]; } } return (int) dp[m]; }}function numDistinct(s: string, t: string): number { const n = s.length, m = t.length; const dp = new Array<number>(m + 1).fill(0); dp[0] = 1; for (let i = 0; i < n; i++) { for (let j = m; j >= 1; j--) { if (s[i] === t[j - 1]) dp[j] += dp[j - 1]; } } return dp[m];}Editorial#
Going right-to-left in j avoids double-counting the current s[i] for the same t[j]. The 2D DP dp[i][j] collapses to a 1D rolling array because each cell only depends on the previous row’s j-1.
Complexity#
- Time: O(n * m).
- Space: O(m).
Concept revision#
Related#