Distinct Subsequences
Given two strings s and t, count how many distinct subsequences of s equal t.
A subsequence is what remains after deleting zero or more characters from s without reordering the rest. Two subsequences are distinct when they use different positions of s, even when the characters they spell are identical.
Input & Output
Input
s — the source string to draw subsequences from
t — the target string the subsequences must spell
Output
the number of distinct subsequences of s that equal t
Example
Input
s = "rabbbit", t = "rabbit"
Output
3
Explanation
s holds three bs and "rabbit" needs two of them, so the choices are the 1st and 2nd b, the 1st and 3rd, or the 2nd and 3rd. Each choice picks a different set of positions, so all three count.
Example
Input
s = "babgbag", t = "bag"
Output
5
Explanation
Indexing "babgbag" from zero, b sits at 0, 2, 4; a at 1, 5; and g at 3, 6. The position sets that increase left to right are (0,1,3), (0,1,6), (0,5,6), (2,5,6), and (4,5,6).
Constraints
1 <= s.length, t.length <= 1000sandtconsist of English letters