DSA problem
Distinct Subsequences
Given two strings s and t, return the number of distinct subsequences of s which equal t. The test cases are generated so that the answer fits on a 32-bit signed integer.
This is a counting variant of LCS. Instead of asking the length of the longest common subsequence, we ask: in how many ways can we pick characters of s (in order) so the picked characters spell t exactly?
The exponential brute force tries every subset of s. Dynamic programming compresses the work by tabulating prefix counts.
Define dp[i][j] as the number of distinct subsequences of s[0..i) that equal t[0..j). The base cases are dp[i][0] = 1 for all i (the empty target has exactly one matching empty subsequence) and dp[0][j] = 0 for j > 0 (empty s cannot match a non-empty t). The recurrence:
- If
s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + dp[i-1][j]— use this character ofsto matcht[j-1](givingdp[i-1][j-1]ways) or skip it (givingdp[i-1][j]ways). - Else:
dp[i][j] = dp[i-1][j]— the only option is to skips[i-1].
The 2D table costs O(m * n) time and space. Since each row depends only on the previous, the space can be compressed to a single 1D array iterated right-to-left.
Examples
s = "rabbbit", t = "rabbit"3s = "babgbag", t = "bag"5s = "", t = "a"0Constraints
- 1 <= s.length, t.length <= 1000
- s and t consist of English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.