Start here (everyday picture). You and a friend each wrote down your favourite songs. The lists are different, but a few songs show up on both — and importantly, in the same order: maybe you both listed "Hey Jude" before "Yesterday" before "Let It Be". The longest run of items you can pick from each list while keeping them in order (you are allowed to skip the others, but never to reorder) is the Longest Common Subsequence. The crucial word is subsequence: skipping is fine, shuffling is not.
Name the pieces. Call the two sequences $X$ (length $m$) and $Y$ (length $n$). We want the length of the longest ordered run of items that lives inside both. A quick worked example: take $X=\text{ABCBDAB}$ and $Y=\text{BDCAB}$. One common subsequence is $\text{BCAB}$ — trace B, then C, then A, then B left to right and you can find each letter in both words without backtracking. No longer one exists, so here $\text{LCS}=4$.
Build the rule. Compare the last letters of the parts you are looking at. If they match ($X_i=Y_j$), that shared letter can finish a longest run, so the answer is one more than the answer on both shortened strings. If they differ, the last letter of one of them is useless, so you throw one away and keep the better of the two choices. Writing $dp[i][j]$ for the LCS length of the first $i$ letters of $X$ and first $j$ of $Y$ gives the table recurrence $dp[i][j]=dp[i-1][j-1]+1$ on a match, otherwise $dp[i][j]=\max(dp[i-1][j],\,dp[i][j-1])$, with empty-prefix base cases $dp[0][j]=dp[i][0]=0$.
Why it is fast. The table has only $(m+1)(n+1)$ cells and each costs constant work, so filling it is $O(mn)$ time and $O(mn)$ space — vastly better than the $\sim 2^{m}$ cost of testing every possible subsequence by hand. The final length sits in the bottom-right cell $dp[m][n]$, and walking backwards from there (step diagonally on a match, otherwise toward the bigger neighbour) rebuilds one actual LCS string.
Try this in the panel above. The animation runs a generic build-and-compare trace, but the idea grows the same way. (1) Press Next repeatedly and watch the Comparisons counter climb — the LCS table does about $m\cdot n$ comparisons, so on two equal-length inputs it heads toward $n^2$. (2) Drag the n slider from 4 up to 16 and notice the total step count grows roughly with the square of $n$, not linearly — that is what $O(mn)$ feels like. (3) Hit Reset, set speed to 0.25x, and step through one comparison at a time: each tick is one unit of the $O(mn)$ work.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size (vertices V, edges E, or array length)
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average-case complexity
h
Height or depth of structure
k
Number of distinct values / items
Step 1 -- Optimal Substructure. If X[m]==Y[n]: LCS(X,Y) = LCS(X[1..m-1], Y[1..n-1]) + 1. If X[m]!=Y[n]: LCS(X,Y) = max(LCS(X[1..m-1], Y), LCS(X, Y[1..n-1])). This shows overlapping subproblems -- exponential naive recursion, O(mn) with memoization.
Step 2 -- Recurrence. dp[i][j] = LCS length of X[1..i] and Y[1..j]. dp[i][j] = dp[i-1][j-1]+1 if X[i]==Y[j]. dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise. Base: dp[0][j]=dp[i][0]=0.
Step 3 -- Time O(mn) Space O(mn). Two nested loops: O(mn). Table: O(mn). Space optimization: only need previous row -> O(n) space. But can't backtrack with O(n) space (need Hirschberg's algorithm for O(n) space + O(mn) time backtrack).
Step 4 -- Backtracking. Start at dp[m][n]. If X[i]==Y[j]: character is in LCS, move to dp[i-1][j-1]. Else if dp[i-1][j] >= dp[i][j-1]: move up (dp[i-1][j]). Else: move left (dp[i][j-1]).
Step 5 -- Relation to Edit Distance. Edit Distance (Levenshtein) = m + n - 2*LCS(X,Y) when only insert/delete operations are allowed (no substitution). LCS and Edit Distance are dual problems -- minimize changes or maximize common elements.
Step 6 -- Applications. Version control (git diff -- finding common lines). Bioinformatics (DNA/protein sequence alignment). File comparison (diff utility). Plagiarism detection. Speech recognition. Compiler token comparison.
§4 — Frequently Asked Questions
What is a subsequence vs a substring? concept+
Subsequence: elements in order but not necessarily contiguous. LCS of 'ABCDE' and 'ACE' is 'ACE' (length 3). Substring: must be contiguous. Longest Common Substring uses a different DP. LCS is more flexible but harder to compute.
Why does the DP use max(dp[i-1][j], dp[i][j-1]) for mismatches? concept+
If X[i] != Y[j], the LCS either: excludes X[i] (use X[1..i-1] with full Y) -> dp[i-1][j], or excludes Y[j] (use full X with Y[1..j-1]) -> dp[i][j-1]. Take the maximum.
How is LCS used in bioinformatics? applied+
DNA sequence alignment: find longest common subsequence of two DNA strands to identify evolutionary conservation. BLAST algorithm uses LCS-like scoring. Needleman-Wunsch (global alignment) and Smith-Waterman (local alignment) are generalizations with gap penalties.
What is Hirschberg's algorithm? complex+
Computes LCS in O(mn) time but O(n) space (vs O(mn) standard). Uses divide-and-conquer: find midpoint of optimal path using forward and backward DP passes (each O(mn/2) time, O(n) space), recursively solve two halves. Essential for very long sequences where O(mn) space is infeasible.
How many distinct LCS sequences can exist? nonobv+
Potentially exponential number of distinct LCS strings of the same maximum length. The DP gives LENGTH and ONE specific LCS. To enumerate all LCS: requires exploring all backtracking choices -- can be exponential. In practice, one representative LCS is sufficient.
What is the connection between LCS and Longest Increasing Subsequence? deep+
LIS of sequence A can be reduced to LCS: sort A to get B, then LCS(A,B) = LIS(A). Standard LIS O(n log n) uses patience sorting. LCS in O(mn) is slower for large inputs but shows the structural connection between these classic DP problems.
§5 — Common Misconceptions & Errors
Conceptual Misconceptions
✗ LCS is the same as Longest Common Substring.
✓ Subsequence: not necessarily contiguous. Substring: must be contiguous. LCS of 'ABCDE' and 'ACE' = 'ACE' (length 3). Longest Common Substring = 'A','B','C','D','E' individually max 1 here.
✗ LCS length can exceed min(m,n).
✓ LCS length is at most min(m,n) -- it is bounded by the shorter string's length. LCS cannot be longer than either input.
✗ The DP works with characters only, not other data types.
✓ LCS works for any data type with equality comparison -- characters, integers, objects. Only X[i]==Y[j] comparison needed.
Implementation Errors
✗ Forgetting to initialize the base cases dp[0][j]=dp[i][0]=0.
✓ Empty prefix has no common characters. Forgetting base cases often manifests as wrong values in first row/column, corrupting all dependent cells.
✗ Backtracking using dp[i][j] > dp[i-1][j] instead of X[i]==Y[j] to detect matches.
✓ Must check X[i]==Y[j] to confirm a match (not just that value increased). dp[i][j] > dp[i-1][j] is a necessary but not sufficient condition.
✗ Using LCS DP for Longest Increasing Subsequence directly.
✓ LIS requires a different DP: dp[i] = LIS ending at index i. Or patience sort O(n log n). LCS-based LIS (reduce to LCS with sorted array) is O(n^2), not O(n log n).