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

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.