# Distinct Subsequence Pattern Matching

Let's solve the Distinct Subsequence Pattern Matching problem using Dynamic Programming.

## Statement

Given two strings, `str1`

and `str2`

, return the number of times `str2`

appears in `str1`

as a subsequence.

Note:A string $X$ is a subsequence of string $Y$ if deleting some number of characters from $Y$ results in the string $X$.

Let’s assume that you have two strings as follows:

`str1 = "bbagbag"`

`str2 = "bag"`

In this example, `str2`

appears $7$ times in `str1`

as a subsequence:

- bbagbag
- bbagbag
- bbagbag
- bbagbag
- bbagbag
- bbagbag
- bbagbag

**Constraints:**

- 1 $\leq$
`str1.length`

,`str2.length`

$\leq$ 500 `str1.length`

$\geq$`str2.length`

`str1`

and`str2`

consist of lowercase English letters

## Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.