Hard · Dynamic Programming

Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s that equal t. Two subsequences are different when they use different index positions of s.

Examples

Example 1

{
  "s": "rabbbit",
  "t": "rabbit"
}

Output: 3 ways

Example 2

{
  "s": "babgbag",
  "t": "bag"
}

Output: 5 ways

Rebuild it in the studio

Open every published interview problem, solution, scene, and memory room free, with no account.