Distinct Subsequences
HardDynamic Programming
You are given two strings s and t. Count how many different ways you can pick characters from s, keeping their original order, so that the picked characters spell exactly t.
Two ways are different if they use a different set of positions in s, even if the resulting text is the same. In other words, return the number of subsequences of s (by index) that equal t. Return 0 if there are none.
Example 1
- Input:
- s = "abcbc", t = "abc"
- Output:
- 3
- Explanation
- The
ais at index 0. Then pick thebat 1 with thecat 2 or 4, or thebat 3 with thecat 4, giving 3 ways.
Example 2
- Input:
- s = "aaaaa", t = "aaa"
- Output:
- 10
- Explanation
- Any 3 of the 5 positions spell
aaa, and there are 5 choose 3 = 10 ways to choose them.
Example 3
- Input:
- s = "abc", t = "abcd"
- Output:
- 0
- Explanation
tis longer thans, so it cannot be a subsequence.
Constraints
- 1 ≤
s.length,t.length≤ 1000 sandtconsist of English letters (case-sensitive)- The answer fits in a signed 32-bit integer