Hard

Quiz

#115 Distinct Subsequences

APPROACH

Count the number of distinct ways that string s contains string t as a subsequence, and return that count.

Inputs are guaranteed to produce an answer that fits within a 32-bit signed integer.

Example 1:

Input: s = "rabbbit", t = "rabbit"

Output: 3

Explanation:

As shown below, there are 3 ways you can generate "rabbit" from s.

rabbbit

Example 2:

Input: s = "babgbag", t = "bag"

Output: 5

Explanation:

As shown below, there are 5 ways you can generate "bag" from s.

babgbag

1 of 4

1:00

What is the optimal approach for this problem?