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