115. Distinct Subsequences

115

HardTwo-Dimensional Dynamic Programming2D dynamic programming over two string prefixesSubsequence-count DP

Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s that equal t. A subsequence is formed by deleting zero or more characters of s without changing the order of the remaining characters. The answer fits in a 32-bit signed integer.

Open official problem prompt ↗

In plain English

Count how many distinct order-preserving selections of characters in s spell out t exactly.

Picture it like this

Imagine t is a word you must spell using beads threaded on a string s in fixed order. You may skip beads but not reorder them. The task is to count how many different sets of beads spell the word.

Example

Input: s = "rabbbit", t = "rabbit"
Output: 3
Why: There are three ways to keep r-a-b-b-i-t by choosing which two of the three b's to use.

Constraints

1 <= s.length, t.length <= 1000s and t consist of English lettersThe answer is guaranteed to fit in a 32-bit signed integer

Pattern lesson

See the pattern, then code

Subsequence-count DP

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. For each character of s you either skip it or, if it matches the current target character, use it. dp[i][j] counts ways to form t[:j] from s[:i], and the used/skip branches add up.

New words, made simpleKnow these before the algorithm

Subsequence: Characters kept in original order after deleting some (possibly none)
State dp[i][j]: Number of ways the first i chars of s produce the first j chars of t
Skip vs use: The two branches: ignore s[i-1], or consume it when it matches t[j-1]

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate all subsequences

Exponentially many subsequences; hopeless for m up to 1000.

Generate every subsequence of s and count those equal to t.

Time O(2^m)Space O(m)

Best choice2D counting DP

Each state computed once by addition; handles the full constraint range.

Build a table where each cell sums a skip branch and (when characters match) a use branch.

Time O(m*n)Space O(m*n), reducible to O(n)

The rule we keep true

Invariant

dp[i][j] always equals the exact number of distinct subsequences of s[:i] that spell t[:j], with dp[i][0] = 1 because the empty target is matched by the single empty selection.

Why this is correct

Reasoning

Partition all matchings of t[:j] inside s[:i] by whether they use the last character s[i-1]. Matchings that skip it are counted by dp[i-1][j]; matchings that use it exist only when s[i-1]==t[j-1] and are counted by dp[i-1][j-1]. The two groups are disjoint and exhaustive, so their sum is exact.

The algorithm in three movesSay these aloud before coding

1Let dp[i][j] be the number of ways s[:i] forms t[:j]

dp[*][0] = 1 (empty target)

2Every s[:i] forms the empty t in exactly one way, so dp[i][0] = 1

at the three b's, counts accumulate

3Always inherit dp[i-1][j] (skip s[i-1])

dp[7][6] = 3

4If s[i-1] == t[j-1], also add dp[i-1][j-1] (use the match)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readt prefix empty

2 · AskHow many ways to form the empty string?

3 · Update statedp[i][0] = 1 for all i

4 · ResultOne way: choose nothing

Key takeaway

String s = rabbbit; the three highlighted b's are the choices that produce three distinct matchings.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-7Table and empty-target base
dp is (m+1)x(n+1); every dp[i][0] is 1 since the empty t is always matchable.
2
Lines 8-12Skip then maybe use
dp[i][j] first inherits the skip count dp[i-1][j], then adds dp[i-1][j-1] when the characters match.
3
Lines 13Return total
dp[m][n] is the number of distinct subsequences of s equal to t.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

t longer than s yields 0
t equal to s yields 1
t empty yields 1 (the base column encodes this)
Repeated characters in s (like the b run) are exactly what create multiple counts

Common beginner mistakes

Overwriting dp[i][j] with only the match branch and forgetting the mandatory skip inheritance
If compressing to 1D, iterating j in the wrong direction and corrupting the diagonal term
Assuming distinct means distinct strings; here distinct means distinct index selections

Check your understanding

When s[i-1] matches t[j-1], why do we add dp[i-1][j-1] on top of dp[i-1][j] rather than replacing it?

Distinct Subsequences

Distinct Subsequences

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming