Distinct Subsequences

The key idea

Let dp[i][j] be the number of distinct subsequences of the first i characters of s that equal the first j characters of t. When s[i-1] == t[j-1] you can either use that character of s (add dp[i-1][j-1]) or skip it (add dp[i-1][j]); when they differ you can only skip it (dp[i-1][j]). The empty target is always matched exactly one way.

Problem

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A subsequence of a string is a new string formed from the original by deleting some (possibly zero) characters without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde" while "aec" is not. Two subsequences are counted as distinct when they keep characters from different positions of s, even if the resulting string is the same. The answer is guaranteed to fit in a 32-bit signed integer.

Constraints

1 <= s.length, t.length <= 1000
s and t consist of English letters.

Examples

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

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

Complexity

Time: O(m * n) Space: O(m * n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →