Longest Common Subsequence: A Visual Walkthrough

Q: What is the time and space complexity of the longest common subsequence algorithm?

The standard tabulation approach runs in O(mn) time and O(mn) space, where m and n are the lengths of the two strings. You can reduce space to O(min(m, n)) using a rolling array, but only if you need the length alone. Recovering the actual subsequence requires the full table because the backtracking step reads cells from multiple rows.

Q: Is there a way to solve LCS faster than O(mn) ?

For the general case, O(mn) is the standard bound. There are theoretical improvements using the Hunt-Szymanski algorithm that run faster when the number of matching character pairs is small, but these rarely matter for interview length inputs. The tabulation approach is what interviewers expect, and the 2D table gives you both the length and the ability to recover the actual subsequence through backtracking. Optimizing beyond O(mn) typically isn't worth the added complexity unless you're working with very long sequences in a production system, not in a 45-minute interview.

Build the longest common subsequence recurrence from scratch, trace the 2D table cell by cell, and recover the actual subsequence step by step.

10 minutes

Intermediate

What you will learn

How the LCS recurrence relation is derived from first principles

How to fill the 2D DP table cell by cell with a concrete example

How to backtrack through the table to recover the actual subsequence

Where LCS connects to Edit Distance, SCS, and other DP patterns

How does the longest common subsequence algorithm actually work? Not the memorized recurrence you copy from a solution, but the reasoning behind it. If you can't explain why the match case uses the diagonal and the no match case doesn't, you don't understand LCS yet. You've just memorized a formula.

⚡TL;DR

LCS builds a 2D table where each cell answers one question: what's the longest subsequence common to these two prefixes? The recurrence has exactly two cases. This article derives both from scratch and traces them cell by cell.

What the longest common subsequence is (and isn't)

The longest common subsequence of two strings is the longest sequence of characters that appears in both strings in the same relative order, but not necessarily contiguously. It's solved with a 2D DP table where each cell stores the LCS length of two prefixes, one from each string.

That "not necessarily contiguously" part is where most confusion starts. A subsequence preserves order but allows gaps. A substring requires every character to be adjacent, with nothing skipped between them.

Take "ABCDE" and "ACE". The longest common substring is just "A" (length 1), because no multi character adjacent sequence appears in both. The longest common subsequence is "ACE" (length 3). A, C, and E appear in both strings in the same order, even though B and D sit between them in the first string.

This distinction matters in interviews. Getting it wrong means building the wrong recurrence entirely. If the problem says "subsequence," you're working with gaps. If it says "substring," you're working with contiguity. A different constraint means a different DP transition and different table behavior on mismatches.

Building the recurrence from scratch

The standard recurrence gets stated as a formula without motivation. So let's build it from the ground up.

You have two strings, s1 of length m and s2 of length n. You want dp[i][j], the LCS length for the first i characters of s1 and the first j characters of s2.

Every cell in the table answers a single question: given these two prefixes, what's the longest common subsequence?

Case 1, the characters match: If s1[i-1] == s2[j-1] (using 0-indexed strings), this character must be part of an optimal subsequence for these prefixes. You take whatever LCS you had for the shorter prefixes and extend it by one. That gives you dp[i][j] = dp[i-1][j-1] + 1.

Case 2, they don't match: If the characters differ, at least one of them isn't in the LCS for these prefixes. You don't know which one to drop, so you try both options. Drop the last character of s1 (giving dp[i-1][j]) or drop the last character of s2 (giving dp[i][j-1]). You take the better result. That gives you dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

The base case: Is straightforward. If either prefix is empty, there's no common subsequence. So dp[0][j] = 0 for all j, and dp[i][0] = 0 for all i.

That covers the whole recurrence in just two cases and a base case. If you're comfortable with recursive thinking, you'll see the connection: each cell's answer depends on smaller subproblems, and the table stores those answers instead of recomputing them. The hard part isn't the formula. It's understanding why the match case uses the diagonal (dp[i-1][j-1]) while the no match case uses the cell above and the cell to the left.

💡 Tip

The diagonal in Case 1 matters because you're consuming one character from both strings simultaneously. If you used dp[i-1][j] + 1 instead, you'd potentially count the same character from s2 twice across different paths. The diagonal ensures each matched character gets counted exactly once.

Filling the table cell by cell

Let's work through a concrete trace. Take s1 = "ABCDE" and s2 = "ACE".

The table has 6 rows (0 through 5, for empty string through "ABCDE") and 4 columns (0 through 3, for empty string through "ACE"). Initialize the entire first row and first column to 0.

Python

Let's walk through the key rows.

Row 1 (A): s1[0] is 'A', which matches s2[0] = 'A'. So dp[1][1] = dp[0][0] + 1 = 1. The remaining cells carry that 1 forward because 'A' doesn't match 'C' or 'E', and max(dp[0][j], dp[1][j-1]) stays at 1.

Row 2 (B) is boring. 'B' doesn't appear in s2 at all, so every cell copies the better of its top or left neighbor. The entire row stays at 1.

Row 3 (C) is where it gets interesting. s1[2] = 'C' matches s2[1] = 'C', so dp[3][2] = dp[2][1] + 1 = 2. The LCS of "ABC" and "AC" is now 2: the subsequence "AC".

Then row 5 (E): s1[4] = 'E' matches s2[2] = 'E', giving dp[5][3] = dp[4][2] + 1 = 3. The final answer is an LCS length of 3.

You see three diagonal jumps across five rows, one per matching character. Every other cell just propagated the best value sideways or downward without adding a new match.

Recovering the actual subsequence

The table gives you the length. To recover the actual characters, you backtrack from dp[m][n].

Python

This is just the table construction in reverse. At each cell, check whether the value came from a diagonal match or from propagation. If the characters match, that character belongs in the LCS and you move diagonally. If they don't, follow whichever neighbor contributed the current value.

For our example, start at dp[5][3] = 3. E matches E, so go diagonal to dp[4][2] = 2. D doesn't match C, and dp[3][2] = 2 is greater than dp[4][1] = 1, so go up. C matches C, go diagonal to dp[2][1] = 1. B doesn't match A, and dp[1][1] = 1 is greater than dp[2][0] = 0, so go up. A matches A, which means you move diagonally to the origin. Reversing the collected characters gives you A, C, E.

“The table tells you the length. The backtrack tells you the path. Both follow from the same two case recurrence.”

LCS construction principle

Where LCS connects to other DP patterns

LCS isn't just one isolated problem but a pattern family. Once you understand the two case recurrence, several harder problems turn out to be variations of it.

Edit Distance: Uses the same 2D table structure, but the no match case splits into three operations (insert, delete, replace) instead of two. The match case is identical, dp[i-1][j-1] with zero penalty. If you can fill an LCS table, you already understand the skeleton of Edit Distance. Both build on recursive subproblem decomposition, which is why understanding recursion deeply makes DP table construction feel natural rather than formulaic.

Shortest Common Supersequence: It is LCS flipped around. The SCS length equals m + n minus the LCS length. You use the LCS to identify shared characters, then fill in everything else. You solve LCS first and reconstruct from there.

Longest Palindromic Subsequence: Reduces to LCS of the string and its reverse. If you want the longest subsequence that reads the same forward and backward, you're asking: what's the LCS of s and reverse(s)?

LCS shows up outside interviews too. The diff utility in version control is fundamentally an LCS computation between two file versions. It's kind of wild that the same two case recurrence powers something you use every day.

More problems reduce to LCS than you'd expect. The core logic (match or skip, tracked across two sequences) appears anywhere two sequences need alignment. For a broader view of where LCS fits among DP patterns, see the complete guide to dynamic programming.

Common mistakes and how to avoid them

Confusing subsequence with substring: For longest common substring, a mismatch resets the cell to 0 instead of propagating the maximum. Mix them up and you'll get wrong answers for any case where matched characters aren't adjacent.
Off by one indexing: The table is (m+1) by (n+1), not m by n. The extra row and column represent the empty prefix. Forget them and your base case collapses, leaving the first match cell with no diagonal to reference.
Assuming one unique LCS exists: Two strings can have multiple longest common subsequences of the same length. "ABCB" and "BDCAB" have LCS length 3, but both "BCB" and "BAB" qualify. Which one you recover depends on how you break ties when the cell above and the cell to the left are equal.
Skipping base case initialization: If you don't initialize dp[0][j] and dp[i][0] to 0, your first matching cell reads whatever the language defaults to. Python list comprehensions handle this automatically. C++ and Java arrays need explicit zeroing.
Optimizing space too early: The standard approach uses O(m * n) space. You can reduce it to O(min(m, n)) with a rolling array, but that only works for the length. Recovering the actual subsequence requires the full table. You should get the basic version working first.

⚠️ Warning

If an interview problem asks you to return the subsequence itself (not just its length), you need the full table. Space optimized LCS only gives you the length. Mention this trade off to your interviewer before choosing your approach.

The reasoning that transfers

LCS is one of those DP problems where the recurrence is short but the reasoning transfers to dozens of variations. If you can trace the table cell by cell and explain why each cell has its value (not just what the value is), you've built understanding that holds up when the problem changes shape.

That's what interleaved practice across related patterns does. You don't master LCS by solving it ten times. You master it by solving LCS, then Edit Distance, then Shortest Common Supersequence, and noticing how the same two case structure adapts each time. If you're still building your foundation for how memoization and tabulation differ, the memoization vs tabulation comparison covers when each approach wins.

Codeintuition's Dynamic Programming course covers LCS as part of a five pattern sequence where each pattern builds on the previous one's reasoning. The LCS lesson traces every cell's value with visual walkthroughs before you write any code. That frame by frame tracing is what turns memorized formulas into actual understanding.

A month ago, you'd see a string alignment problem and code the recurrence from memory. A constraint you hadn't seen would stop you cold. Now you trace the table. You know why the match case uses the diagonal. You know why the no match case tries both directions. When the next variation arrives, you adjust the recurrence instead of searching for a different template.

Start here and work forward from there.

Trace DP tables cell by cell before writing code

Codeintuition's Dynamic Programming course covers LCS, Edit Distance, and four other DP families with visual walkthroughs that trace every cell's value. Build the recurrence from the decision, not from memory. Start FREE with two full courses.

Start Learning

The standard tabulation approach runs in O(mn) time and O(mn) space, where m and n are the lengths of the two strings. You can reduce space to O(min(m, n)) using a rolling array, but only if you need the length alone. Recovering the actual subsequence requires the full table because the backtracking step reads cells from multiple rows.

A subsequence preserves character order but allows gaps between matched characters. A substring requires every matched character to be adjacent with no gaps. In the DP table, the difference shows up on mismatches. LCS propagates the maximum from neighboring cells, while longest common substring resets to zero. This makes LCS length always greater than or equal to longest common substring length for any pair of strings. So two strings like "ABCDE" and "ACE" have an LCS of length 3 but a longest common substring of only length 1.

Yes, and this surprises many people during interviews. Multiple subsequences of the same maximum length can exist. For example, "ABCB" and "BDCAB" both produce an LCS of length 3, but "BCB" and "BAB" are equally valid. Which one the backtracking algorithm returns depends on how you break ties when dp[i-1][j] equals dp[i][j-1].

Look for problems comparing two sequences where you need to find shared structure while preserving order. Keywords like "common," "subsequence," "minimum insertions to make equal," and "supersequence" often signal an LCS family problem.

For the general case, O(mn) is the standard bound. There are theoretical improvements using the Hunt-Szymanski algorithm that run faster when the number of matching character pairs is small, but these rarely matter for interview length inputs. The tabulation approach is what interviewers expect, and the 2D table gives you both the length and the ability to recover the actual subsequence through backtracking. Optimizing beyond O(mn) typically isn't worth the added complexity unless you're working with very long sequences in a production system, not in a 45-minute interview.