Distinct Subsequences
Hard · Dynamic Programming · about 25 minutes
Asked at Meta, Microsoft, Amazon, Google.
Count the ways to pick characters from s, in order, that spell out t. Two ways differ if they use different positions of s, even when the letters are the same. The count fits in a signed 32-bit integer.