Skip to content

148 — Distinct Subsequences

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

148 — Distinct Subsequences

LeetCode 115 · Hard. Given two strings s and t, return the number of distinct subsequences of s which equal t. A subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions.

🍽️ Intuition

Picture scanning s left to right while trying to "spell out" t using a subset of s's characters, in order. At each character of s, there are two choices when it happens to match the next needed character of t: use it to advance through t, or skip it and hope a later copy of that character shows up. Counting all the distinct ways to make those choices work out is exactly "how many ways can the first i characters of s produce the first j characters of t," a question that only needs two smaller sub-answers — the same question with one fewer character of s, either advancing through t or not — which is the two-index signature of 2-D DP.

🚩 Pattern-Recognition Cue

"Count distinct subsequences of s that equal t" is the two-string counting-DP tell: the state is (how far into s, how far into t), and — unlike Interleaving String's either/or boolean — the answer at each cell is a count, summing the "skip this character of s" possibilities with the "use this character of s to match t" possibilities whenever the characters agree.

🐢 Brute Force

Recurse over (i, j) — how far into s and t — always allowed to skip the current character of s, and additionally allowed to consume it to match t when the characters agree, with no memoization.

func numDistinctBruteForce(_ s: String, _ t: String) -> Int {
    let a = Array(s), b = Array(t)

    func count(_ i: Int, _ j: Int) -> Int {
        if j == b.count { return 1 }     // all of t matched: one valid way found
        if i == a.count { return 0 }     // ran out of s before matching all of t

        var total = count(i + 1, j)      // skip s[i]
        if a[i] == b[j] {
            total += count(i + 1, j + 1) // use s[i] to match t[j]
        }
        return total
    }

    return count(0, 0)
}

// smoke test
print(numDistinctBruteForce("rabbbit", "rabbit"))   // 3
print(numDistinctBruteForce("babgbag", "bag"))       // 5
print(numDistinctBruteForce("aa", "a"))              // 2

Big-O: O(2^m) time in the worst case, where m = s.count — every character of s that matches the current position in t branches two ways, and the same (i, j) pairs are re-explored down many different branches. O(m) space for the recursion stack.

🚀 Optimal

Fill an (m+1) x (n+1) table where dp[i][j] is the number of distinct subsequences of the first i characters of s equal to the first j characters of t — every row starts with dp[i][0] = 1 (there's exactly one way to match the empty string: delete everything).

func numDistinct(_ s: String, _ t: String) -> Int {
    let a = Array(s), b = Array(t)
    let m = a.count, n = b.count
    guard n <= m else { return 0 }

    var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
    for i in 0...m {
        dp[i][0] = 1
    }
    guard n > 0 else { return 1 }

    for i in 1...m {
        for j in 1...n {
            dp[i][j] = dp[i - 1][j]                 // always allowed to skip s[i-1]
            if a[i - 1] == b[j - 1] {
                dp[i][j] += dp[i - 1][j - 1]         // additionally, use s[i-1] to match t[j-1]
            }
        }
    }
    return dp[m][n]
}

// smoke test — same cases as the brute force
print(numDistinct("rabbbit", "rabbit"))   // 3
print(numDistinct("babgbag", "bag"))       // 5
print(numDistinct("aa", "a"))              // 2

Big-O: O(m · n) time — every cell is filled exactly once from at most two already-known neighbors. O(m · n) space for the dp table (collapsible to O(n) with a single rolling row, filled right to left).

🔑 The Key Insight

Both versions make the same choice at every (i, j) — skip the current character of s, and additionally use it if it matches — but the brute force treats every (i, j) as fresh no matter how many branches arrive at it, so the same suffix-matching sub-problems are re-solved exponentially many times. The optimal version fills the table row by row, so dp[i-1][j] and dp[i-1][j-1] are always finished answers by the time dp[i][j] needs them. Summing (not choosing the max of) two already-solved neighbors instead of re-branching from scratch is what turns exponential subsequence counting into a flat O(m · n) table fill.

🔗 Related Chapters

  • 2D Dynamic Programming — two sequences, one on each axis, with cells summing (rather than maxing) their neighbors — a variation on the recognition signal in chapter 27 for counting problems instead of optimization problems.
  • Arrays and Strings — both strings are converted to [Character] arrays for O(1) indexed access, and dp is a plain 2-D array of counts.

🧸 Memory Sentence

Distinct Subsequences sums, it doesn't choose — every cell adds "the ways without this character of s" to "the ways using it to match t," instead of taking the better of the two like Longest Common Subsequence does.

✅ Check Your Understanding

  1. Why is dp[i][0] = 1 for every i, including i = 0, rather than 0? What single subsequence of any string equals the empty string t?
  2. Trace numDistinct("aa", "a") by hand-filling the small 3 x 2 table. Which two subsequences of "aa" does the final count of 2 represent?
  3. Longest Common Subsequence takes max(dp[i-1][j], dp[i][j-1]) on a mismatch, while Distinct Subsequences only ever reads dp[i-1][j] (never dp[i][j-1]) when skipping a character of s. Why doesn't this problem's recurrence need to consider skipping a character of t?

⬅️ Previous: Longest Increasing Path in a Matrix · Next: Edit Distance ➡️

Clone this wiki locally