We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given two strings s and t, return the number of distinct subsequences of s which equals t.
A subsequence of a string is obtained by deleting zero or more characters from the original string while keeping the relative order of the remaining characters. The test cases are guaranteed to fit in a 32-bit signed integer.
A hard dynamic programming problem, graded against 6 test cases (3 of them hidden).
Overlapping subproblems solved once and reused - the pattern candidates fear most.
Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.
More Dynamic Programming problems →`dp[i][j]` = number of ways to form `t[0..j-1]` as a subsequence of `s[0..i-1]`.
- `dp[i][0] = 1` for all i (empty t is always a subsequence, exactly once).
- If `s[i-1] == t[j-1]`: we can either consume this s-char to match t's j-th, contributing `dp[i-1][j-1]`, or skip the s-char, contributing `dp[i-1][j]`.
- Else: must skip the s-char, `dp[i][j] = dp[i-1][j]`.
Iterating j right-to-left lets us collapse to a 1D array of size |t|+1.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
These apply to the pattern as a whole, not just this problem.