17 lines (12 loc) · 308 Bytes

Problem 19: Distinct Subsequences

Problem Statement

Count the number of distinct subsequences of s that equal t.

Input Format

Two strings s and t.

Output Format

An integer.

Constraints

1 <= len(s), len(t) <= 1000

Example

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