Distinct Subsequences
HardP3Coding
Return the number of distinct subsequences of s that equal t. Subsequences are distinguished by which positions of s they use, so the same text formed from different positions counts several times.
Example 1
- Input
- s = "rabbbit", t = "rabbit"
- Output
- 3
- Why
- Three ways to drop one of the three `b` letters.
Example 2
- Input
- s = "babgbag", t = "bag"
- Output
- 5
- Why
- Five position choices spell `bag`.
Example 3
- Input
- s = "a", t = "a"
- Output
- 1
Constraints
- 1 <= t.length <= s.length <= 1000
- Both strings contain English letters.
- The answer fits in a 53-bit integer.
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 12. ⌘Enter runs, ⌘⇧Enter submits.