Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s that equal t. Pattern focus: Distinct subsequences. This is the canonical count-the-ways DP problem on two strings.

Input Format

s = source string, t = target string

Output Format

number of distinct subsequences of s equal to t

Constraints

  • 0 <= s.length, t.length <= 1000
  • s and t contain lowercase English letters.

Examples

Example 1:

Input:

s = "rabbbit"
t = "rabbit"

Output:

3

Explanation:

There are three ways to delete one of the b characters.

Example 2:

Input:

s = "babgbag"
t = "bag"

Output:

5

Explanation:

This is the classic example for counting subsequences.

Loading...
Distinct Subsequences - Dp Strings DSA Problem