Room 04 · The Grind — 2-D Dynamic Programming

Distinct Subsequences

HARD✓ CHIP-TIMEDLC #115 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Count the distinct ways to obtain a shorter string by deleting characters from a longer one, without reordering what's left — every deletion pattern that lands exactly on the target counts once.

Two strings arrive: a longer source and a shorter target. The task is counting how many distinct ways letters can be deleted from the source — without disturbing the order of what's left — so the remainder reads exactly like the target.

Two deletion patterns count separately whenever they keep characters from different positions in the source, even when the surviving text looks identical. A repeated letter at several source positions can each anchor its own path to the same match.

Totals can climb fast when the source repeats letters heavily, since many independent deletion paths can land on the same target text — the count of paths is what gets reported, not any single path.

source string is typically longer than the target, sometimes by a lot
both strings use plain letters, and lengths stay in easily workable ranges
an empty target counts as reachable in exactly one way — deleting everything
path counts are reported as exact integers, however large they grow

EX 01

s = "applesauce" · t = "ale"

→ 2

the board's example

EX 02

s = "" · t = ""

→ 1

two empty strings — one trivial match

EX 03

s = "hello" · t = ""

→ 1

empty target always matches once, by deleting everything

The hintstake only what you need

HINT 1 THE NUDGE

At the first character of the longer string you always have two options — use it or skip it — and using it is only legal when it currently matches the next needed character of the target. Where does the branching actually come from?

HINT 2 THE STRUCTURE

Recurse on a pair of positions, one per string. Skipping never moves the target position; matching (when the characters agree) advances both. What happens once the target position reaches the end of the target?

HINT 3 ONE STEP FROM THE ANSWER

dp(i, j) = dp(i+1, j) [skip] plus dp(i+1, j+1) when s[i] == t[j] [use it]. Base cases: dp(i, len(t)) = 1 for any i — the target is already fully matched — and dp(len(s), j) = 0 whenever j < len(t).

Coach's boardthe pattern, step by step

COUNTING THE DELETIONSPATTERN · MEMO ON (i, j)s = "bab" · t = "ab"

STEP 1

s='bab', t='ab'. dp[i][j] counts ways to match t[j:] using s[i:]. Base column j=2 (target already empty) is1 for every row.

STEP 1 / 5 · ← → WORK TOO

The splitstwo paces, two languages

grind/distinct-subsequences.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        # dp[i][j] = ways to match t[j:] using s[i:]
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][m] = 1

        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                dp[i][j] = dp[i + 1][j]
                if s[i] == t[j]:
                    dp[i][j] += dp[i + 1][j + 1]

        return dp[0][0]

TIME O(M·N)SPACE O(M·N)PYTHON · RACE PACE · 15 LN

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)

        def rec(i, j):
            if j == m:
                return 1
            if i == n:
                return 0
            count = rec(i + 1, j)          # skip s[i]
            if s[i] == t[j]:
                count += rec(i + 1, j + 1)  # use s[i] to match t[j]
            return count

        return rec(0, 0)

TIME O(2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 15 LN

class Solution {
    public int numDistinct(String s, String t) {
        int n = s.length(), m = t.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][m] = 1;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i][j] += dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
}

TIME O(M·N)SPACE O(M·N)JAVA · RACE PACE · 18 LN

class Solution {
    private String s, t;
    private int n, m;

    public int numDistinct(String s, String t) {
        this.s = s;
        this.t = t;
        n = s.length();
        m = t.length();
        return rec(0, 0);
    }

    private int rec(int i, int j) {
        if (j == m) return 1;
        if (i == n) return 0;
        int count = rec(i + 1, j);
        if (s.charAt(i) == t.charAt(j)) {
            count += rec(i + 1, j + 1);
        }
        return count;
    }
}

TIME O(2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED