Longest Common Subsequence (LeetCode 1143)
You're handed two strings, text1 and text2. A subsequence of a string is whatever remains after deleting zero or more of its characters while keeping the survivors in their original order -- for instance, "ace" can be pulled out of "abcde" this way. A common subsequence is a subsequence the two strings share.
Report the length of the longest subsequence they have in common, or 0 if they share none.
Worked Examples
text1 = "abcde", text2 = "ace"3text1 = "abc", text2 = "abc"3text1 = "abc", text2 = "def"0⚖️Formal Constraints & Bounds
1 <= text1.length, text2.length <= 1000text1andtext2consist of only lowercase English characters.
Core Insight
Defining the subproblem on string prefixes turns full comparison into a 2-D recurrence: match extends diagonal by 1; mismatch takes the maximum of dropping the current character from either string.
Real-World Scenario & Production Applications
Git diff algorithm (Myers diff), DNA sequence alignment in computational genomics (BLAST/Smith-Waterman), and fuzzy text similarity.
Subproblems & Recurrence Decomposition3 Phases
Define dp[i][j] as the length of the Longest Common Subsequence between prefix text1[:i] and prefix text2[:j]. Empty prefixes initialize to 0 (dp[0][j] = 0, dp[i][0] = 0).
# dp[i][j] = LCS length of text1[:i] and text2[:j]
dp = [[0] * (N + 1) for _ in range(M + 1)]Step-by-Step Execution Trace Table
dp[i][j] | "" | a | c | e |
|---|---|---|---|---|
"" | 0 | 0 | 0 | 0 |
a | 0 | 1 (diagonal match) | 1 | 1 |
b | 0 | 1 | 1 | 1 |
c | 0 | 1 | 2 (diagonal match) | 2 |
d | 0 | 1 | 2 | 2 |
e | 0 | 1 | 2 | 3 (diagonal match Final Answer) |
| 1 | dp = [[0] * (n + 1) for _ in range(m + 1)] |
| 2 | for i in range(1, m + 1): |
| 3 | for j in range(1, n + 1): |
| 4 | if text1[i-1] == text2[j-1]: |
| 5 | dp[i][j] = dp[i-1][j-1] + 1 |
| 6 | else: |
| 7 | dp[i][j] = max(dp[i-1][j], dp[i][j-1]) |
| 8 | return dp[m][n] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Longest Common Subsequence aligns two strings $s_1$ and $s_2$. At cell $(i, j)$ of the 2D DP matrix, if characters match (`s_1[i-1] == s_2[j-1]`), the alignment extends diagonally: $dp[i][j] = dp[i-1][j-1] + 1$. If they differ, the optimal alignment discards one character from either string: $dp[i][j] = max(dp[i-1][j], dp[i][j-1])$. This evaluates all prefix subproblems in $O(M \times N)$ time and $O(min(M, N))$ space. 🧩 The Analogy: Aligning Two Rows of Puzzle Pieces
Imagine laying two strings out as two rows of labeled tiles, and you're building an alignment table cell by cell. At cell (i, j), you're asking: "what's the longest common subsequence between the first i letters of text1 and the first j letters of text2?" If the two letters at this position match, you get to extend the alignment diagonally — the answer here is 1 more than whatever the alignment was before both letters were added (dp[i-1][j-1]). If they don't match, you can't extend a match here at all, so you inherit the best alignment achievable by dropping just one letter from either string — whichever of dp[i-1][j] or dp[i][j-1] is bigger.
🔑 The Key Idea in the Code
A match always moves diagonally (both strings advance together); a mismatch always moves orthogonally (only one string advances) — this is why LCS's DP table is famously visualized with diagonal arrows tracing the matched characters.
1-based DP table coordinate shift off-by-one: Forgetting that table cell
dp[i][j]maps to string indicestext1[i - 1]andtext2[j - 1]. Comparingtext1[i] == text2[j]causes string out-of-bounds or misaligned character comparisons.Mismatch transition cost: Adding on mismatch states:
1 + max(dp[i-1][j], dp[i][j-1]). Mismatch transitions carry no reward; the recurrence is strictlymax(dp[i-1][j], dp[i][j-1]).Diagonal overwrite in 1D space optimization: In rolling 1D space, updating
dp[j]overwrites the value from the previous row thatdp[j+1]needs as its top-left diagonal neighbordp[i-1][j-1]. A temporary variableprevmust store the diagonal value before overwriting.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Subsequence alignment between two strings + ordering preserved + finding longest shared elements.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Recurrence: if s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Off-by-one indexing: grid dimensions must be (M+1) x (N+1) so row 0 and col 0 represent empty string prefixes.
Allocating 2D grid with shallow copies (e.g.
[[0]*(N+1)]*(M+1)in Python) which causes mutated rows.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use a 2D DP table of size (M+1) x (N+1). When characters match, I extend the optimal prefix alignment from dp[i-1][j-1] by 1. On mismatch, I take the maximum of dropping a character from text1 or text2. This yields an optimal O(M * N) time and space solution."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: 2D DP table of size M x N where text1 has length M and text2 has length N. Transition: if characters match, 1 + diag; else max(top, left). Rolling rows reduces space to O(min(M, N)).
O(min(M, N)) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Two rows of size min(M, N) + 1.
T(M, N) = M · N = O(M · N)
Derivation Progression
dp[i][j] = LCS(text_1[:i], text_2[:j])
(M+1) x (N+1) discrete alignment subproblems.
if t1[i-1] == t2[j-1]: 1 + dp[i-1][j-1] else max(top, left)
Constant-time transition arithmetic.
O(min(M, N)) row storage
Only previous row is needed for current row calculations.
Variable Definitions
Length of first string text1
Length of second string text2
Memory Architecture & Bounds
O(1) Iterative
O(min(M, N)) Two 1D arrays of size min(M, N)
O(1) LCS length integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest common subsequence of two strings". 2D prefix string alignment: - If : match diagonal . - Else: take max of deleting from () or ().
. Time budget: operations (ms).
1-indexed DP coordinates avoid negative index checks on empty string base cases.
Longest Common Subsequence (LeetCode 1143)
You're handed two strings, text1 and text2. A subsequence of a string is whatever remains after deleting zero or more of its characters while keeping the survivors in their original order -- for instance, "ace" can be pulled out of "abcde" this way. A common subsequence is a subsequence the two strings share.
Report the length of the longest subsequence they have in common, or 0 if they share none.
Worked Examples
text1 = "abcde", text2 = "ace"3text1 = "abc", text2 = "abc"3text1 = "abc", text2 = "def"0⚖️Formal Constraints & Bounds
1 <= text1.length, text2.length <= 1000text1andtext2consist of only lowercase English characters.
Core Insight
Defining the subproblem on string prefixes turns full comparison into a 2-D recurrence: match extends diagonal by 1; mismatch takes the maximum of dropping the current character from either string.
Real-World Scenario & Production Applications
Git diff algorithm (Myers diff), DNA sequence alignment in computational genomics (BLAST/Smith-Waterman), and fuzzy text similarity.
Subproblems & Recurrence Decomposition3 Phases
Define dp[i][j] as the length of the Longest Common Subsequence between prefix text1[:i] and prefix text2[:j]. Empty prefixes initialize to 0 (dp[0][j] = 0, dp[i][0] = 0).
# dp[i][j] = LCS length of text1[:i] and text2[:j]
dp = [[0] * (N + 1) for _ in range(M + 1)]Step-by-Step Execution Trace Table
dp[i][j] | "" | a | c | e |
|---|---|---|---|---|
"" | 0 | 0 | 0 | 0 |
a | 0 | 1 (diagonal match) | 1 | 1 |
b | 0 | 1 | 1 | 1 |
c | 0 | 1 | 2 (diagonal match) | 2 |
d | 0 | 1 | 2 | 2 |
e | 0 | 1 | 2 | 3 (diagonal match Final Answer) |
| 1 | dp = [[0] * (n + 1) for _ in range(m + 1)] |
| 2 | for i in range(1, m + 1): |
| 3 | for j in range(1, n + 1): |
| 4 | if text1[i-1] == text2[j-1]: |
| 5 | dp[i][j] = dp[i-1][j-1] + 1 |
| 6 | else: |
| 7 | dp[i][j] = max(dp[i-1][j], dp[i][j-1]) |
| 8 | return dp[m][n] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Longest Common Subsequence aligns two strings $s_1$ and $s_2$. At cell $(i, j)$ of the 2D DP matrix, if characters match (`s_1[i-1] == s_2[j-1]`), the alignment extends diagonally: $dp[i][j] = dp[i-1][j-1] + 1$. If they differ, the optimal alignment discards one character from either string: $dp[i][j] = max(dp[i-1][j], dp[i][j-1])$. This evaluates all prefix subproblems in $O(M \times N)$ time and $O(min(M, N))$ space. 🧩 The Analogy: Aligning Two Rows of Puzzle Pieces
Imagine laying two strings out as two rows of labeled tiles, and you're building an alignment table cell by cell. At cell (i, j), you're asking: "what's the longest common subsequence between the first i letters of text1 and the first j letters of text2?" If the two letters at this position match, you get to extend the alignment diagonally — the answer here is 1 more than whatever the alignment was before both letters were added (dp[i-1][j-1]). If they don't match, you can't extend a match here at all, so you inherit the best alignment achievable by dropping just one letter from either string — whichever of dp[i-1][j] or dp[i][j-1] is bigger.
🔑 The Key Idea in the Code
A match always moves diagonally (both strings advance together); a mismatch always moves orthogonally (only one string advances) — this is why LCS's DP table is famously visualized with diagonal arrows tracing the matched characters.
1-based DP table coordinate shift off-by-one: Forgetting that table cell
dp[i][j]maps to string indicestext1[i - 1]andtext2[j - 1]. Comparingtext1[i] == text2[j]causes string out-of-bounds or misaligned character comparisons.Mismatch transition cost: Adding on mismatch states:
1 + max(dp[i-1][j], dp[i][j-1]). Mismatch transitions carry no reward; the recurrence is strictlymax(dp[i-1][j], dp[i][j-1]).Diagonal overwrite in 1D space optimization: In rolling 1D space, updating
dp[j]overwrites the value from the previous row thatdp[j+1]needs as its top-left diagonal neighbordp[i-1][j-1]. A temporary variableprevmust store the diagonal value before overwriting.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Subsequence alignment between two strings + ordering preserved + finding longest shared elements.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Recurrence: if s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Off-by-one indexing: grid dimensions must be (M+1) x (N+1) so row 0 and col 0 represent empty string prefixes.
Allocating 2D grid with shallow copies (e.g.
[[0]*(N+1)]*(M+1)in Python) which causes mutated rows.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use a 2D DP table of size (M+1) x (N+1). When characters match, I extend the optimal prefix alignment from dp[i-1][j-1] by 1. On mismatch, I take the maximum of dropping a character from text1 or text2. This yields an optimal O(M * N) time and space solution."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: 2D DP table of size M x N where text1 has length M and text2 has length N. Transition: if characters match, 1 + diag; else max(top, left). Rolling rows reduces space to O(min(M, N)).
O(min(M, N)) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Two rows of size min(M, N) + 1.
T(M, N) = M · N = O(M · N)
Derivation Progression
dp[i][j] = LCS(text_1[:i], text_2[:j])
(M+1) x (N+1) discrete alignment subproblems.
if t1[i-1] == t2[j-1]: 1 + dp[i-1][j-1] else max(top, left)
Constant-time transition arithmetic.
O(min(M, N)) row storage
Only previous row is needed for current row calculations.
Variable Definitions
Length of first string text1
Length of second string text2
Memory Architecture & Bounds
O(1) Iterative
O(min(M, N)) Two 1D arrays of size min(M, N)
O(1) LCS length integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest common subsequence of two strings". 2D prefix string alignment: - If : match diagonal . - Else: take max of deleting from () or ().
. Time budget: operations (ms).
1-indexed DP coordinates avoid negative index checks on empty string base cases.