Distinct Subsequences

Asked byAmazonMathworksGoogle

Problem

Given two strings s and t, return the number of distinct subsequences of s that equal t.

Example 1

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

Output:3

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

The same DP idea as 1-D, but the state depends on two indices — often two positions in a grid, or a position in each of two sequences being compared.

You're comparing two sequences (finding a longest common subsequence, edit distance).
You're computing paths or optimal values across a 2-D grid.