115. Distinct Subsequences
Given two strings s and t, count how many distinct subsequences of s spell exactly t. A subsequence deletes zero or more characters of s without reordering what remains. Two subsequences count separately when they keep different positions of s, even if the text they produce looks identical: with s = "aab" and t = "ab", either a can start the match, so the count is 2.
Your function receives s and t and returns the count as an integer. The inputs are chosen so the answer fits in a signed 64-bit integer.
Example 1:
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation: s has three b's but t needs only two, so "rabbit" can be traced through s in three ways — one per choice of which b to drop.
Example 2:
Input: s = "babgbag", t = "bag"
Output: 5
Explanation: Five different position sets of s spell "bag": (0,1,3), (0,1,6), (0,5,6), (2,5,6) and (4,5,6) in "babgbag".
Constraints:
- 1 ≤ s.length ≤ 1000
- 1 ≤ t.length ≤ 1000
- s and t consist of English letters
- The answer fits in a signed 64-bit integer
Hints:
Compare one character of s at a time against t. If the current s character cannot extend a match it changes nothing; if it equals some t character you face a choice — consume it or skip it. Choices multiply: that is a counting recurrence, not a search.
Define dp[i][j] = the number of ways the first i characters of s spell the first j characters of t. Then dp[i][j] = dp[i-1][j], plus dp[i-1][j-1] when s[i-1] == t[j-1], with dp[i][0] = 1 (one way to spell the empty prefix). Fill the table — or keep a single row and update j from right to left.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "rabbbit", t = "rabbit"
Expected output: 3