Overview
The Longest Common Subsequence (LCS) problem asks for the longest sequence of characters that appears in both input strings in the same relative order, though not necessarily contiguously. It is a textbook example of dynamic programming, where a two-dimensional DP table lets us reuse the answers to overlapping subproblems instead of re-solving them.
By filling a table where cell dp[i][j] holds the LCS length of the first i characters of one string and the first j of the other, the algorithm solves the whole problem in O(m·n) time — a huge improvement over the exponential naive recursion. LCS underpins tools like diff and version control merges.
How Longest Common Subsequence works
- Create an (m+1)×(n+1) DP table and initialise the first row and column to 0 — an empty prefix shares no subsequence.
- Fill the table row by row, comparing character i of the first string with character j of the second.
- If the two characters match, set dp[i][j] = dp[i-1][j-1] + 1 — extend the diagonal subproblem by one.
- If they differ, take the better of dropping one character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
- The bottom-right cell holds the LCS length; trace back through the table to recover the actual subsequence.
When to use it
- Powering diff utilities and source-control merges that highlight what two file versions share.
- Bioinformatics — measuring similarity between DNA, RNA, or protein sequences.
- Plagiarism detection and fuzzy text matching, where overlapping content matters.
- As a building block for related edit-based measures such as the diff/patch line model.
Complexity analysis
Filling every cell of the (m+1)×(n+1) table costs O(m·n) time and O(m·n) space in the straightforward version. Since each row depends only on the previous one, the space can be reduced to O(min(m,n)) by keeping just two rows — though that trade-off makes reconstructing the subsequence itself harder.
Frequently asked questions
What is the difference between a subsequence and a substring?
A substring must be contiguous, while a subsequence only needs to keep the relative order of its characters and may skip over others. 'ace' is a subsequence of 'abcde' but not a substring.
Why is dynamic programming faster than the naive recursion here?
The naive recursion re-solves the same overlapping subproblems exponentially many times. The DP table caches each subproblem's answer once, so the total work drops to the O(m·n) distinct cells.
Can there be more than one longest common subsequence?
Yes. Multiple subsequences can share the maximum length; the DP gives the length uniquely, but the traceback may choose any one of several equally long answers depending on tie-breaking.