Overview
The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both in the same relative order, not necessarily contiguously. For "abcde" and "ace", the LCS is "ace" with length 3.
dp[i][j] is the LCS length of the first i characters of text1 and the first j of text2. If the last characters match, extend the diagonal: dp[i - 1][j - 1] + 1. Otherwise drop a character from one side: max(dp[i - 1][j], dp[i][j - 1]). LCS is the template for many string comparison problems.
Two friends list songs in the order they like them. The LCS is the longest list of songs both have in the same relative order, even if other songs are mixed in between.
When to use it
- Measure similarity between two sequences while preserving order.
- Minimum deletions or insertions to transform one string into another.
- Shortest common supersequence.
- Longest palindromic subsequence (LCS of s and reverse(s)).
Problem patterns it solves
Recognize it when: longest shared ordered sequence.
- 1143. Longest Common Subsequence
- 1035. Uncrossed Lines
Recognize it when: minimum deletions = m + n - 2 x LCS.
- 583. Delete Operation for Two Strings
- 712. Minimum ASCII Delete Sum for Two Strings
Recognize it when: shortest string containing both as subsequences = m + n - LCS.
- 1092. Shortest Common Supersequence
Recognize it when: palindromic subsequence, minimum insertions for a palindrome.
- 516. Longest Palindromic Subsequence
- 1312. Minimum Insertion Steps to Make a String Palindrome
Recognize it when: longest common substring or subarray: reset to 0 on mismatch.
- 718. Maximum Length of Repeated Subarray
Recognize it when: is s a subsequence of t (two pointers, a special case).
- 392. Is Subsequence
- 792. Number of Matching Subsequences
Where it is used in real software
Unix diff and git diff use LCS-based algorithms (Myers' algorithm) on lines to show added and removed lines.
Comparing documents or code by the longest shared ordered token sequences.
Comparing DNA sequences to find conserved regions between species.
Three-way merge tools align versions by common subsequences before detecting conflicts.
Key terms
- Subsequence
- Characters in order, gaps allowed.
- Substring
- Contiguous characters; different DP (reset on mismatch).
- Diagonal move
- Characters match: dp[i - 1][j - 1] + 1.
- Reconstruction
- Walk back from dp[m][n] to output the actual subsequence.
How it works, step by step
- 1Table of size (m + 1) x (n + 1)
Row 0 and column 0 are 0 (empty prefix).
- 2Match
text1[i - 1] === text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1.
- 3No match
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
- 4Answer
dp[m][n].
- 5Reconstruct
From (m, n): on a match go diagonal and record the character; otherwise move toward the larger neighbor.
LCS of "abcde" and "ace"
Rows: prefixes of abcde; columns: "", a, c, e
| "" | a | c | e | |
|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 |
| a | 0 | 1 (match) | 1 | 1 |
| b | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 2 (match) | 2 |
| d | 0 | 1 | 2 | 2 |
| e | 0 | 1 | 2 | 3 (match) |
NOW: "" | "": 0 | a: 0 | c: 0 | e: 0
dp[5][3] = 3. Walking back through the three diagonal matches gives "ace".
Implementation
function longestCommonSubsequence(a, b) { const m = a.length, n = b.length; const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0)); for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]); } } // Reconstruct the subsequence let i = m, j = n; const chars = []; while (i > 0 && j > 0) { if (a[i - 1] === b[j - 1]) { chars.push(a[i - 1]); i--; j--; } else if (dp[i - 1][j] >= dp[i][j - 1]) i--; else j--; } return { length: dp[m][n], sequence: chars.reverse().join("") };} // O(min(m, n)) space for the length onlyfunction lcsLength(a, b) { if (a.length < b.length) [a, b] = [b, a]; let prev = new Array(b.length + 1).fill(0); for (let i = 1; i <= a.length; i++) { const cur = new Array(b.length + 1).fill(0); for (let j = 1; j <= b.length; j++) { cur[j] = a[i - 1] === b[j - 1] ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]); } prev = cur; } return prev[b.length];}Complexity and performance
Every pair of prefixes.
Reduce to O(min(m, n)) for the length only.
Walk back through the table.
Trade-offs
You need the full table (or Hirschberg's algorithm) to reconstruct the subsequence; two rows suffice for the length.
LCS allows only insertions and deletions; edit distance also allows substitutions.
Variants and related techniques
Reconstructs the LCS in O(min(m, n)) space using divide and conquer.
Generalizes to a k-dimensional table, exponential in k.
When one string is a permutation, LCS reduces to LIS in O(n log n).
Common mistakes
- Confusing subsequence and substring versions.
Fix: Subsequence takes max of neighbors on mismatch; substring resets to 0.
- Indexing text[i] instead of text[i - 1].
Fix: With a padded table, row i corresponds to character i - 1.
Interview questions
Why does a mismatch take the maximum of two neighbors?
If the last characters differ, at least one of them is not in the LCS, so the answer is the better of dropping the last character from text1 or from text2.
How do you get the longest palindromic subsequence from LCS?
Compute the LCS of the string and its reverse; any common subsequence of both is a palindrome.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| 392. Is Subsequence | Easy | Two pointers special case. |
| 1143. Longest Common Subsequence | Medium | Core table. |
| 583. Delete Operation for Two Strings | Medium | LCS formula. |
| 718. Maximum Length of Repeated Subarray | Medium | Contiguous variant. |
| 1312. Minimum Insertion Steps to Make a String Palindrome | Hard | LCS with reverse. |
| 1092. Shortest Common Supersequence | Hard | Reconstruction. |