Distinct Subsequences

Walk s and t together. At each character of s, either it is used to match the current character of t (only possible if they are equal), or it is skipped over. Both choices can be valid at once when the characters match — skipping still counts, because a later matching occurrence of the same character in s might be needed for a different subsequence.

Brute Force Recursion

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

At index i in s and j in t: if s[i] == t[j], count both “use this character” (advance both pointers) and “skip it” (advance only i). If they differ, the only option is to skip.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        def rec(i: int, j: int) -> int:
            if j == n:
                return 1
            if i == m:
                return 0
            skip = rec(i + 1, j)
            take = rec(i + 1, j + 1) if s[i] == t[j] else 0
            return skip + take
        return rec(0, 0)

Every character of s can independently be used or skipped, and the same (i, j) pair recurs across many branches — exponential blow-up.

2-D DP Table (Bottom-Up)

OptimalTime O(m·n)Space O(m·n)

dp[i][j] is the number of ways to form t[0:j] as a subsequence of s[0:i]. Column 0 (t empty) is always 1 — the empty subsequence is formed exactly one way, by skipping everything. Row 0 (s empty, t non-empty) is always 0. Every other cell always inherits “skip s[i-1]” (dp[i-1][j]), and additionally adds “match s[i-1] to t[j-1]” (dp[i-1][j-1]) when the characters agree.

class Solution:
    def numDistinct(self, 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]

Filling the table cell by cell for s = "rara", t = "ra" — watch how every cell copies from above (skip the current s char) and, when the two characters match, also adds the diagonal (use that char to advance t).

t →

s ∅100

r1··

a1··

r1··

a1··

base cases

dp[i][0] = 1, every row: empty t matched one way

dp[0][j] = 0, row 0: empty s cannot spell t

all other cells start unfilled (·)

1 / 9

cell being computedcell-source (above / diagonal)

Base cases: column 0 is the empty t, so dp[i][0] = 1. Row 0 is the empty s with non-empty t, so dp[0][j] = 0.

There are 3 ways to spell ra from rara: positions (r@0,a@1), (r@0,a@3), and (r@2,a@3).

Complexity: each of the (m+1)·(n+1) cells does O(1) work → O(m·n) time, O(m·n) space.

1-D Rolling Array

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

Row i reads only from row i-1, at columns j and j-1. Iterating columns right to left within a single reused row lets dp[j-1] still hold last row’s value when it’s read (it hasn’t been overwritten yet this pass), while dp[j] gets updated in place.

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

Same O(m·n) time, but only one row of length n + 1 is kept — O(n) space.

Distinct Subsequences

Brute Force Recursion

2-D DP Table (Bottom-Up)

1-D Rolling Array

More 2-D DP practice