115. Distinct Subsequences

Practice Distinct Subsequences for free on NudgeCode: Hard, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Count the ways to delete characters from s (keeping the rest in order) so that what remains equals t. Two ways are different if they keep a different set of positions from s.

Example

s = "rabbbit", t = "rabbit"  ->  3   (drop any one of the three b's)
s = "babgbag", t = "bag"     ->  5

Constraints

• 1 <= s.length, t.length <= 1000
• Both strings are English letters
• The answer fits in a 32-bit signed integer