Distinct Subsequences
Implement numDistinct
Given two strings
s and t, count how many distinct ways there are to pick a subset of positions in s (keeping their original order) so that the characters at those positions spell out t exactly. Two ways are different if they use a different set of positions from s, even when the resulting characters look identical (repeated letters matter).
Every matched position in s either gets used to satisfy the next needed character of t or gets skipped, so this is a natural fit for tracking, at every prefix-length pair (i, j), how many ways there are to have already matched the first j characters of t using only the first i characters of s. That count always carries forward everything a shorter prefix of s already achieved (skipping s[i-1] changes nothing), and — only when s[i-1] happens to equal the character t is currently waiting on — picks up one more source of matches: every way the previous state matched one character less. Chaining that rule across the whole grid turns an exponential search into a single pass over an (n+1)×(m+1) table.
Example 1:
Input: s = "rabbbit", t = "rabbit"
Output: 3
Example 2:
Input: s = "babgbag", t = "bag"
Output: 5
Example 3:
Input: s = "", t = "abc"
Output: 0
+ 8 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ s.length, t.length ≤ 10 - ●
s and t consist of lowercase English letters - ●
the answer is guaranteed to fit in a 32-bit signed integer for the given ranges
s =
rabbbit
t =
rabbit