Distinct Subsequences

Distinct Subsequences is a classic grid dynamic-programming problem. It teaches you to count possibilities — not just find one answer — by filling a 2D table where each cell builds on its neighbors.

The slow way first

The brute-force idea is to generate every subsequence of s and count how many equal t. A string of length n has 2ⁿ subsequences, so this is exponential — hopeless for anything but tiny inputs.

The question to ask: as I scan s and t together, what smaller answer can I reuse? If I already know how many ways a shorter prefix of t fits inside a shorter prefix of s, I can extend that to the full strings one character at a time. That is exactly what a DP grid stores.

The idea: a counting grid

Build a table dp where dp[i][j] is the number of ways the first j characters of t appear as a subsequence inside the first i characters of s. The answer is the bottom-right cell.

For each cell we always have the option to skip s[i-1], which gives us dp[i-1][j]. If the current characters match (s[i-1] == t[j-1]), we additionally get the option to use s[i-1] to satisfy t[j-1], which adds the diagonal dp[i-1][j-1].

The base cases anchor everything: an empty t matches any prefix of s in exactly one way (delete everything), so the first column is all 1. An empty s cannot contain any non-empty t, so the rest of the top row is 0.

Walk through it

Step through the animation. The grid fills top to bottom, left to right. Watch the column for t's b: as s gains its first, second, and third b, that count climbs 1 → 2 → 3, because each extra b is another independent choice. The unique i and t at the end just carry that count straight down to the final cell, 3.

Pseudocode

let dp be an (m+1) x (n+1) grid of zeros   # m = len(s), n = len(t)
for every row i:
    dp[i][0] = 1                            # empty t matches one way
for i from 1 to m:
    for j from 1 to n:
        dp[i][j] = dp[i-1][j]               # always: skip s[i-1]
        if s[i-1] == t[j-1]:
            dp[i][j] += dp[i-1][j-1]         # also: use s[i-1] for t[j-1]
return dp[m][n]

The Python solution

def num_distinct(s, t):
    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):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[m][n]

• dp is an (m+1) × (n+1) grid; the extra row and column hold the empty-string base cases.
• The loop dp[i][0] = 1 fills the first column: an empty t is matched exactly one way for every prefix of s.
• When s[i-1] == t[j-1], we sum two choices: dp[i-1][j-1] uses this character of s, and dp[i-1][j] skips it.
• When the characters differ, the only option is to skip s[i-1], so we copy dp[i-1][j].
• The answer is dp[m][n], the bottom-right cell, after the whole grid is filled.

Complexity

We trade an O(m × n) table for an enormous speedup. The space can be reduced to O(n) by keeping only the previous row, since each cell looks back only one row.

When this pattern shows up

Practice