Distinct Subsequences
Given two strings s and t, count how many distinct subsequences of s are equal to t — that is, how many different ways you can delete characters from s (keeping the rest in order) so that what remains reads exactly t. Two ways are different if they keep different sets of positions, even when the resulting text looks the same.
Constraints: 1 <= s.length, t.length <= 1000, and the answer fits in a signed 32-bit integer.
Examples
- Input:
- s = "rabbbit", t = "rabbit"
- Output:
- 3
Delete any one of the three middle b's: rabb_it, rab_bit, ra_bbit all leave "rabbit".
- Input:
- s = "babgbag", t = "bag"
- Output:
- 5
Five position-sets spell bag: (b1,a1,g1), (b1,a1,g2), (b1,a2,g2), (b2,a2,g2), (b3,a2,g2).
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.