Interleaving String

mediumTests passed 2026-11-11v1.0.0
TC: O(M * N)|SC: O(min(M, N))
2D DPStringsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Check `len(s1) + len(s2) == len(s3)` first. State `(i, j)` tracks whether `s1[:i]` and `s2[:j]` interleave to form `s3[:i + j]`. Rolling 1D row: `dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])`.

2. Complexity Bounds & Proof

Rolling 1D boolean array computes reachability across the M×N prefix grid with zero backtracking exponential blowup.

3. Minimal Idiomatic Code

def isInterleave(s1: str, s2: str, s3: str) -> bool:
    if len(s1) + len(s2) != len(s3):
        return False
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    dp = [False] * (len(s2) + 1)
    dp[0] = True
    for j in range(1, len(s2) + 1):
        dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
    for i in range(1, len(s1) + 1):
        dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
        for j in range(1, len(s2) + 1):
            dp[j] = (dp[j] and s1[i - 1] == s3[i + j - 1]) or (dp[j - 1] and s2[j - 1] == s3[i + j - 1])
    return dp[-1]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Skipping length guard `len(s1) + len(s2) != len(s3)` either crashes indexing or accepts trailing leftover characters. - Forgetting `dp[0]` updates during row transitions (row `i > 0` column `0` requires `dp[0] and s1[i-1] == s3[i-1]`).
Follow-ups:- Distinct Subsequences uses the exact same 1D counting structure on `(s, t)`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Longest Common Subsequence (O(M * N))Edit Distance (O(M * N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.