How do you approach Distinct Subsequences?

Let dp[i][j] = number of distinct subsequences of s[0..i-1] that equal t[0..j-1].

What is the time complexity of Distinct Subsequences?

Time complexity: O(|s| · |t|). Space complexity: O(|t|) with the 1D rollover.

What are common mistakes on Distinct Subsequences?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Distinct Subsequences

HardAlgorithms

Description

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.

Example 1

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

Output: 3

Explanation: There are three ways to form rabbit from rabbbit by deleting one b (positions 2, 3, or 4).

Example 2

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

Output: 5

Constraints

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

Distinct Subsequences: approach, complexity and pitfalls

A hard dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

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 Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Let dp[i][j] = number of distinct subsequences of s[0..i-1] that equal t[0..j-1].
If s[i-1] == t[j-1], dp[i][j] = dp[i-1][j-1] (use this char) + dp[i-1][j] (skip it). Else dp[i][j] = dp[i-1][j].
Base: dp[i][0] = 1 (empty t matches anything one way), dp[0][j>0] = 0.

The optimal approach

Show the approach: 2D DP (Edit-Distance Family)

`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.

Time: O(|s| · |t|)
Space: O(|t|) with the 1D rollover

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.