Longest Common Subsequence

mediumTests passed 2026-11-11v1.0.0

TC: O(M * N)|SC: O(min(M, N))

2D DP Strings Original Statement (leetcode).md

1. Core Invariant / The Trick

Rolling 1D DP tracking previous diagonal `diag`: if `text1[i] == text2[j]`, extend `diag + 1`; otherwise `max(dp[j], dp[j - 1])`. Space drops from `O(M * N)` to `O(min(M, N))`.

2. Complexity Bounds & Proof

Swap strings so shorter string dictates 1D row length `N`; each step reads current `dp[j]` (above), `prev` (left), and `diag` (top-left).

3. Minimal Idiomatic Code

def longestCommonSubsequence(text1: str, text2: str) -> int:
    if len(text1) < len(text2):
        text1, text2 = text2, text1
    dp = [0] * (len(text2) + 1)
    for c1 in text1:
        diag = 0
        for j, c2 in enumerate(text2, 1):
            up = dp[j]
            dp[j] = diag + 1 if c1 == c2 else max(dp[j], dp[j - 1])
            diag = up
    return dp[-1]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Failing to save `tmp = dp[j]` into `diag` *before* overwriting `dp[j]` loses the top-left diagonal value.

Follow-ups:- Shortest Common Supersequence reconstructs through full 2D table of `dp[i][j]` with string length `M + N - LCS`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

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

Related Invariants

Edit Distance (O(M * N))Interleaving String (O(M * N))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.