Distinct Subsequences

1. Problem & Core Objective

Return the number of distinct subsequences of s that equal t. A subsequence deletes zero or more characters without reordering the rest.

s = "rabbbit", t = "rabbit"   →  3      three ways to pick which 'b's to keep
s = "babgbag", t = "bag"      →  5

Constraints: 1 <= s.length, t.length <= 1000 · letters only · the answer fits in a 32-bit integer

What's actually being tested: an asymmetric two-sequence recurrence. Unlike LCS, the two strings play different roles — s may skip characters freely, t may not. That asymmetry shows up as dp[i-1][j] appearing in both branches, which is the line most people get wrong.

2. First-Principles Thought Process

The two strings are not symmetric

In LCS, either string could drop a character. Here:

• s may skip any character — that's what "subsequence" permits
• t must be matched entirely, in order, with nothing skipped

So the recurrence can't be symmetric, and recognising that is the whole problem.

The state

dp[i][j] = the number of ways s's first i characters can form t's first j.

The recurrence

Consider s[i-1], the last character of s's prefix. Two cases:

It doesn't match t[j-1]. Then it can't be used, so skip it:

dp[i][j] = dp[i-1][j]

It matches. Now there's a choice — use it to match t[j-1], or skip it and match t[j-1] with an earlier character of s:

dp[i][j] = dp[i-1][j-1]  +  dp[i-1][j]
           └── use it ──┘    └─ skip it ─┘

Both options are counted, because they produce genuinely different subsequences — different positions of s are selected.

That + dp[i-1][j] in the match case is the line that's easy to omit, and omitting it undercounts badly.

Why dp[i][0] = 1

There's exactly one way to form the empty string from any prefix of s: delete everything. So the entire first column is 1.

Setting it 0 zeroes the whole table.

Why dp[0][j] = 0 for j > 0

An empty s can't form a non-empty t. Java's zero-initialisation gives this, but only after dp[0][0] = 1 is set separately.

3. Solution Paths

Approach 1 — Recursion

public int numDistinct(String s, String t) {
    return count(s, t, s.length(), t.length());
}

private int count(String s, String t, int i, int j) {
    if (j == 0) return 1;                            // t fully matched: one way
    if (i == 0) return 0;                            // s exhausted, t isn't

    int ways = count(s, t, i - 1, j);                // skip s[i-1]
    if (s.charAt(i - 1) == t.charAt(j - 1))
        ways += count(s, t, i - 1, j - 1);           // ALSO use it
    return ways;
}

• Time O(2^m) · Space O(m) stack

Counter-questions on this approach

⭐ "Why is the skip branch outside the if?"

Because skipping s[i-1] is always legal, whether or not it matches. s is the string allowed to drop characters.

The match only adds an extra option — using the character — on top of the skip that was already available. Putting the skip inside an else would be the classic error: it would force a match whenever one is possible, missing every subsequence that skips a usable character.

On "rabbbit" → "rabbit", that would return 1 instead of 3.

⭐ "Why does j == 0 return 1 rather than 0?"

Because t has been fully matched — the empty remainder is satisfied by taking nothing more. One complete way.

Returning 0 would make every path contribute nothing.

And the order matters: j == 0 must be checked before i == 0, because when both are 0 the answer is 1, not 0.

"How slow is it?"

2^m with m = 1000 — hopeless. Only m × n = 10^6 distinct states exist.

Approach 2 — 2-D tabulation

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) dp[i][0] = 1;       // one way to form "" — delete everything

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];                             // skip s[i-1]
            if (s.charAt(i - 1) == t.charAt(j - 1))
                dp[i][j] += dp[i - 1][j - 1];                    // also use it
        }

    return dp[m][n];
}

Trace — s = "babgbag", t = "bag":

Answer 5 ✓

• Time O(m · n) = 10^6 · Space O(m · n) ≈ 4 MB

Counter-questions on this approach

⭐ "Why does the match case ADD rather than replace?"

Because both choices produce distinct subsequences. Using s[i-1] to match t[j-1] selects one set of positions; skipping it and matching with an earlier character selects a different set.

Both are valid and they're different, so the counts add.

On "rabbbit" matching "rabbit", the three answers differ only in which of the three bs is dropped — that's exactly this addition accumulating.

⭐ "Why is the whole first column 1?"

dp[i][0] counts ways to form the empty t from s's first i characters: delete all of them. Exactly one way, for every i.

Setting dp[0][0] = 1 alone isn't enough — the column must be seeded throughout, or the recurrence's skip branch propagates zeros.

"Could the count overflow?"

Yes in principle. With s of 1000 identical characters and t a short prefix of them, the count is a large binomial — C(1000, 3) is already 1.6 × 10^8, and longer t pushes it far past int.

The problem guarantees the answer fits in a signed 32-bit integer, which bounds the actual inputs. That's a guarantee about the test data rather than the input space, same as in Decode Ways.

Approach 3 — Rolled to one row (optimal)

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;                                        // one way to form ""

    for (int i = 1; i <= m; i++)
        for (int j = n; j >= 1; j--)                  // DESCENDING
            if (s.charAt(i - 1) == t.charAt(j - 1))
                dp[j] += dp[j - 1];

    return dp[n];
}

• Time O(m · n) · Space O(n)

Counter-questions on this approach

⭐ "Why does j descend here, when Unique Paths ascended?"

Because the recurrence reads the diagonal dp[i-1][j-1], and in one array that's the previous row's value at j-1.

Descending means dp[j-1] hasn't been touched yet this row, so it still holds row i−1. Ascending would have already overwritten it with row i, reading the wrong generation.

Unique Paths ascended because it needed the current row's left neighbour. The direction is dictated by which generation you need — and it's the same read-the-previous-generation discipline as everywhere else.

⭐ "Where did the skip branch go?"

It became implicit. dp[i][j] = dp[i-1][j] means "unchanged from the previous row", and in a single rolled array that's simply not writing — the value stays.

So the code only needs the match case, which adds the diagonal. That's why the rolled version looks so different from the 2-D one, and it's worth stating rather than leaving as a puzzle.

"Why is dp[0] never updated?"

The inner loop stops at j = 1, so dp[0] stays 1 throughout — which is correct, since every prefix of s has exactly one way to form the empty t.

"Can it roll to O(1)?"

No. The recurrence reads a full row of previous values, not a fixed window — same as LCS and Word Break. O(n) is the floor.

Comparison

4. Why the Optimal Wins

The recursion re-explores (i, j) pairs exponentially often.

The modelling content is the asymmetry: s may skip freely, t may not. That produces dp[i-1][j] in both branches — always available as a skip, plus the diagonal when a match offers an extra option.

The framing worth keeping:

s can skip, t cannot. So the skip branch is unconditional and a match only ADDS the diagonal on top. Rolled to one row, j must descend — the diagonal needs the previous row's value at j−1.

5. Java Prerequisites

The asymmetric recurrence

dp[i][j] = dp[i-1][j];                                   // skip: ALWAYS available
if (s.charAt(i-1) == t.charAt(j-1))
    dp[i][j] += dp[i-1][j-1];                            // match: an EXTRA option

Rolled, descending — because the diagonal needs the previous row:

for (int j = n; j >= 1; j--)
    if (s.charAt(i-1) == t.charAt(j-1)) dp[j] += dp[j-1];

Loop direction by generation

First column all 1s — one way to form the empty string.

6. Interview Communication Guide

Clarifying questions: Subsequence, not substring (subsequence — deletions allowed, order preserved)? Do different position-sets count separately even if the resulting string is identical (yes — that's why "rabbbit" gives 3)? Does the answer fit in int (guaranteed)?

The pitch

"The two strings are not symmetric, and that's the crux. s may skip characters — that's what subsequence means — but t must be matched entirely, in order.

So dp[i][j] is the number of ways s's first i characters form t's first j.

Consider the last character of s's prefix. Skipping it is always legal, so dp[i-1][j] is unconditional. If it also matches t's last character, there's an extra option — use it — which adds dp[i-1][j-1].

The two are added, not chosen between, because they produce genuinely different subsequences: different positions of s are selected.

The line people get wrong is putting the skip inside an else. That forces a match whenever one is available, and on 'rabbbit' → 'rabbit' it returns 1 instead of 3 — the three answers differ only in which of the three bs is dropped.

Base case: the entire first column is 1, because there's exactly one way to form the empty string from any prefix — delete everything. Seeding only dp[0][0] isn't enough; the skip branch would propagate zeros.

O(m·n) = 10^6. Rolled to one row it's O(n), with j descending — because the recurrence reads the diagonal, which in one array is the previous row's value at j−1, and ascending would have already overwritten it.

That's the opposite direction from Unique Paths, which ascended because it needed the current row's left neighbour. The direction follows from which generation you need.

In the rolled version the skip branch disappears entirely — 'unchanged from the previous row' is just not writing.

One thing to flag: the count can overflow in principle. With 1000 identical characters the answer is a large binomial. The problem guarantees it fits in int, but that's about the test data rather than the input space."

Edge cases to volunteer:

Name "aaa" / "a". The answer is 3, not 1 — each position of a is a distinct subsequence. A solution that stops at the first match returns 1, which is the same bug as the else mistake.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the subsequences themselves, not the count."

Backtracking — there can be exponentially many, as the binomial counts show. Counting without producing is exactly what the DP buys.

⭐ "Check whether t is a subsequence of s at all."

Far easier: two pointers, O(m + n), no DP. Walk s advancing a pointer into t on each match. Existence and counting have very different costs here — worth naming.

"Count distinct subsequences of s that equal t, where identical results collapse."

A different question. "aaa" → "a" would be 1 rather than 3, because all three produce the same string. That needs deduplication by content, typically by only counting the first occurrence of each character at each position.

"What if t could also skip characters?"

Then it's symmetric and becomes LCS-shaped — counting common subsequences rather than embeddings of a fixed t.

"What if m and n were 10^4?"

O(m·n) = 10^8 — borderline. The rolled version helps memory, not time. And the count would overflow anything short of BigInteger or a modulus.

"Count with at most k characters skipped in s."

Add a dimension for skips used: dp[i][j][k]. O(m·n·k) time and space, rolling to O(n·k).