Distinct Subsequences

Problem

Given two strings s and t, count the number of distinct ways to delete some (possibly zero) characters from s, without reordering the rest, so that the remaining characters spell exactly t. Two ways are different if they delete a different set of positions. Return that count.

A subsequence keeps characters in their original order but need not be contiguous.

Examples

• s = "rabbbit", t = "rabbit" → 3 — three different choices of which b to drop from the three b’s in s produce "rabbit".
• s = "babgbag", t = "bag" → 5 — five distinct index-sets of s spell "bag".
• s = "abc", t = "abcd" → 0 — t is longer than s, so it can never be formed.

Constraints

• 1 <= len(s), len(t) <= 1000 (roughly)
• Both strings consist of English letters.
• The answer fits in a 32-bit signed integer.
• With lengths up to ~1000, an O(len(s)·len(t)) table is the intended complexity; enumerating subsequences (up to 2^len(s)) is impossible.

Think about it first

TL;DR

Two-string DP: dp[i][j] counts how many ways t[:j] is a subsequence of s[:i] — O(len(s)·len(t)) time, O(len(t)) space with a rolling row.

Approach 1 — Brute force recursion

At each character of s you either skip it, or (if it matches the current t character) consume both. Count the paths that consume all of t.

def numDistinct(s: str, t: str) -> int:
    def count(i: int, j: int) -> int:
        if j == len(t):
            return 1                 # matched all of t
        if i == len(s):
            return 0                 # ran out of s with t unfinished
        ways = count(i + 1, j)       # skip s[i]
        if s[i] == t[j]:
            ways += count(i + 1, j + 1)   # use s[i] to match t[j]
        return ways
    return count(0, 0)

Complexity: O(2^len(s)) time in the worst case — every character forks into skip/use. Exponential and infeasible for length-1000 strings.

Approach 2 — Top-down memoization

The insight: the count from position (i, j) onward depends only on (i, j), not on the earlier choices that led there. There are only len(s)·len(t) such states, so caching removes the recomputation.

State / recurrence. count(i, j) = number of ways t[j:] appears as a subsequence of s[i:]. Transition count(i, j) = count(i+1, j) + (count(i+1, j+1) if s[i]==t[j] else 0); base cases count(i, len(t)) = 1 and count(len(s), j<len(t)) = 0.

from functools import lru_cache

def numDistinct(s: str, t: str) -> int:
    @lru_cache(maxsize=None)
    def count(i: int, j: int) -> int:
        if j == len(t):
            return 1
        if i == len(s):
            return 0
        ways = count(i + 1, j)
        if s[i] == t[j]:
            ways += count(i + 1, j + 1)
        return ways
    return count(0, 0)

Complexity: O(len(s)·len(t)) time and space.

Approach 3 — Bottom-up tabulation (the 2-D table)

State / recurrence. dp[i][j] = number of ways the first j characters of t form a subsequence of the first i characters of s.

dp[i][0] = 1                              # empty t: delete everything, one way
dp[0][j] = 0  for j > 0                   # non-empty t from empty s: impossible
dp[i][j] = dp[i-1][j]                     # skip s[i-1]
         + dp[i-1][j-1]  if s[i-1]==t[j-1]  # also use it to match t[j-1]

Each cell takes the value directly above (skip s[i-1]) and, only on a character match, adds the value diagonally above-left:

flowchart TD
    A["dp[i-1][j-1]"] -->|"only if s[i-1] == t[j-1]"| C["dp[i][j]"]
    B["dp[i-1][j]"] -->|"always (skip s[i-1])"| C

def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = 1
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i - 1][j]
            if s[i - 1] == t[j - 1]:
                dp[i][j] += dp[i - 1][j - 1]
    return dp[m][n]

Walkthrough with s = "rabbbit", t = "rabbit". The r and a match uniquely, so the count stays 1 through the "ra" prefix. The count grows where the three b’s in s align against the two b’s in t: each extra b in s adds another choice of which one to skip. By the end of the b run the count reaches 3, and the unique i and t at the tail carry it through to dp[7][6] = 3.

Complexity: O(m·n) time, O(m·n) space.

Approach 4 — Space-optimized rolling row

The insight: dp[i] reads only from dp[i-1]. Keep one array indexed by j and sweep j from high to low so dp[j-1] still holds the previous row’s value (the dp[i-1][j-1] term) when we update dp[j].

def numDistinct(s: str, t: str) -> int:
    n = len(t)
    dp = [0] * (n + 1)
    dp[0] = 1
    for ch in s:
        for j in range(n, 0, -1):
            if ch == t[j - 1]:
                dp[j] += dp[j - 1]
    return dp[n]

Complexity: O(m·n) time, O(n) space.

Common pitfalls

• Getting the base cases backwards: dp[i][0] = 1 for every i (empty target matched by deleting all), but dp[0][j] = 0 for j > 0.
• In the rolling-row version, sweeping j upward, which overwrites dp[j-1] with the current row before it is read — you must go downward.
• Adding the match term unconditionally; it applies only when s[i-1] == t[j-1].
• Confusing this “count of subsequences” with “is t a subsequence of s” (a boolean/greedy problem) — here every distinct index-set counts.

Pattern takeaway

Two-sequence DP indexes a table by a prefix of each string, dp[i][j], and each cell branches on whether the two current characters match. The recurring shape is “skip a character of the source (always) plus, on a match, an aligned diagonal term”. When one dimension only reads the immediately previous row, collapse to a single array — swept in the direction that preserves the diagonal dependency.