Distinct Subsequences

Problem

Given two strings s and t, count how many different ways you can delete characters from s (possibly none) so that what remains equals t. Two ways are different if the sets of kept positions in s differ, even when the kept characters look identical.

• 1 <= len(s), len(t) <= 1000
• Both strings contain only English letters.
• The answer fits in a 32-bit signed integer.

Examples

• s = "googgle", t = "gog" → 4. Position sets (0-based): {0,1,3}, {0,1,4}, {0,2,3}, {0,2,4}.
• s = "catcatcat", t = "cat" → 10. Any of the three cat copies can supply each letter, subject to keeping their relative order.
• s = "xyz", t = "xyzw" → 0. t is longer than s, so nothing can be deleted to reach it.

Hints

1. Walk through s one character at a time and ask how many ways the first i characters of s can produce the first j characters of t.
2. When s[i-1] == t[j-1], you may use that character to match t[j-1], or you may skip it. Both are legitimate and must be added together.
3. dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if s[i-1] == t[j-1] else 0), with dp[i][0] = 1.