Longest Common Subsequence (LCS)
Longest Common Subsequence finds the longest sequence of characters appearing in the same relative order (not necessarily contiguous) in two strings using 2D Dynamic Programming.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Longest Common Subsequence (LCS)
Given two sequences $A$ (length $n$) and $B$ (length $m$), the Longest Common Subsequence (LCS) is the longest sequence that appears as a subsequence in both $A$ and $B$ (characters need not be contiguous, only in the same relative order). LCS is the foundation of git diff, DNA sequence alignment, and Edit Distance.
At a Glance
| Property | Value |
| :--- | :--- |
| Time Complexity | $O(n \cdot m)$ |
| Auxiliary Space | $O(n \cdot m)$ (for reconstruction) / $O(\min(n, m))$ (length only) |
| State Definition | dp[i][j] = LCS length of prefixes A[0..i-1] and B[0..j-1] |
| Best Used When | Diffing text/files, bioinformatics alignment, string similarity, palindrome subsequences |
---
How It Works
For every $1 \le i \le n$ and $1 \le j \le m$:
$dp[i][j] = \begin{cases} dp[i - 1][j - 1] + 1 & \text{if } A[i - 1] = B[j - 1] \\ \max(dp[i - 1][j],\ dp[i][j - 1]) & \text{if } A[i - 1] \ne B[j - 1] \end{cases}$
Base cases: dp[0][j] = 0 and dp[i][0] = 0 (LCS with an empty string is 0).
procedure lcs(A, B):
n = length(A), m = length(B)
dp = (n + 1) x (m + 1) array of 0
for i = 1 to n:
for j = 1 to m:
if A[i - 1] == B[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
Step-by-Step Trace
A = "ABCDE", B = "ACE":
A[0]='A' == B[0]='A'→dp[1][1] = 1A[2]='C' == B[1]='C'→dp[3][2] = dp[2][1] + 1 = 2A[4]='E' == B[2]='E'→dp[5][3] = dp[4][2] + 1 = 3- Result: LCS length =
3("ACE").
---
Complexity & Key Insights
- Space Optimization: Computing just the length only needs the previous row
prevand current rowcur, reducing memory from $O(nm)$ to $O(\min(n, m))$. - Reconstructing the Actual LCS: Walk backward from
(n, m): ifA[i - 1] == B[j - 1], appendA[i - 1]and move diagonally(i - 1, j - 1); otherwise step toward whichever ofdp[i - 1][j]ordp[i][j - 1]is larger. Reverse at the end. - Hidden LCS Problems:
- Longest Palindromic Subsequence (LPS) of
S=LCS(S, reverse(S)). - Shortest Common Supersequence (SCS) length =
n + m - LCS(A, B). - Minimum Deletions to Make Two Strings Equal =
n + m - 2 * LCS(A, B).
---
Practice Problems
Easy
1. Longest Common Subsequence Length (Space-Optimized, LeetCode 1143)
Return the length of the LCS of two strings text1 and text2 in $O(\min(n, m))$ space.
Approach: Roll two 1D rows prev and cur of length m + 1. Time: $O(nm)$. Space: $O(m)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int lcsLength(const std::string& a, const std::string& b) {
int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
std::vector<int> prev(m + 1, 0), cur(m + 1, 0);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i - 1] == b[j - 1]) cur[j] = prev[j - 1] + 1;
else cur[j] = std::max(prev[j], cur[j - 1]);
}
prev.swap(cur);
}
return prev[m];
}
int main() {
std::cout << lcsLength("abcde", "ace") << "\n"; // 3
return 0;
}
</details>
2. Reconstruct the Actual LCS String
Return one actual Longest Common Subsequence string of a and b.
Approach: Fill the full (n + 1) x (m + 1) DP table, then backtrack from (n, m) to (0, 0) and reverse the collected characters. Time: $O(nm)$. Space: $O(nm)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
std::string buildLCS(const std::string& a, const std::string& b) {
int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
std::string res;
int i = n, j = m;
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) {
res.push_back(a[i - 1]);
--i; --j;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
--i;
} else {
--j;
}
}
std::reverse(res.begin(), res.end());
return res;
}
int main() {
std::cout << buildLCS("AGGTAB", "GXTXAYB") << "\n"; // GTAB
return 0;
}
</details>
---
Intermediate
3. Longest Palindromic Subsequence (LeetCode 516)
Given a string s, find the length of its longest palindromic subsequence.
Approach: A palindrome reads the same forward and backward, so LPS(s) = LCS(s, reverse(s)). Time: $O(n^2)$. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int longestPalindromeSubseq(const std::string& s) {
std::string rev(s.rbegin(), s.rend());
int n = static_cast<int>(s.size());
std::vector<int> prev(n + 1, 0), cur(n + 1, 0);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == rev[j - 1]) cur[j] = prev[j - 1] + 1;
else cur[j] = std::max(prev[j], cur[j - 1]);
}
prev.swap(cur);
}
return prev[n];
}
int main() {
std::cout << longestPalindromeSubseq("bbbab") << "\n"; // 4 ("bbbb")
return 0;
}
</details>
4. Shortest Common Supersequence (LeetCode 1092)
Given two strings a and b, return the shortest string that has both a and b as subsequences.
Approach: Compute the LCS table and backtrack from (n, m). Whenever a[i - 1] == b[j - 1], emit the shared character once; otherwise emit the character from whichever side we step away from. Finally append any remaining prefix of a or b and reverse. Time: $O(nm)$. Space: $O(nm)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
std::string shortestCommonSupersequence(const std::string& a, const std::string& b) {
int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
dp[i][j] = (a[i - 1] == b[j - 1]) ? dp[i - 1][j - 1] + 1 : std::max(dp[i - 1][j], dp[i][j - 1]);
std::string res;
int i = n, j = m;
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) { res.push_back(a[i - 1]); --i; --j; }
else if (dp[i - 1][j] >= dp[i][j - 1]) { res.push_back(a[i - 1]); --i; }
else { res.push_back(b[j - 1]); --j; }
}
while (i > 0) res.push_back(a[--i]);
while (j > 0) res.push_back(b[--j]);
std::reverse(res.begin(), res.end());
return res;
}
int main() {
std::cout << shortestCommonSupersequence("abac", "cab") << "\n"; // cabac
return 0;
}
</details>
---
Hard
5. LCS of Two Permutations in $O(n \log n)$
Given two permutations A and B of $\{1, 2, \dots, n\}$ (with $n \le 2 \times 10^5$), find their LCS length in $O(n \log n)$ time!
Approach: Because every value appears once in each permutation, map each value v to its position pos[v] in A. Then a common subsequence of A and B corresponds to a strictly increasing sequence of pos[B[i]]—reducing LCS to $O(n \log n)$ Longest Increasing Subsequence (LIS)!
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int lcsPermutations(const std::vector<int>& A, const std::vector<int>& B) {
int n = static_cast<int>(A.size());
std::vector<int> pos(n + 1);
for (int i = 0; i < n; ++i) pos[A[i]] = i;
std::vector<int> tails;
for (int x : B) {
int idx = pos[x];
auto it = std::lower_bound(tails.begin(), tails.end(), idx);
if (it == tails.end()) tails.push_back(idx);
else *it = idx;
}
return static_cast<int>(tails.size());
}
int main() {
std::cout << lcsPermutations({3, 2, 1, 4, 5}, {1, 2, 3, 4, 5}) << "\n"; // 3 (e.g. 1,4,5)
return 0;
}
</details>
---
Related Algorithms
- Edit Distance — extends LCS with insertion, deletion, and replacement costs.
- Longest Increasing Subsequence (LIS) — solves LCS on permutations in $O(n \log n)$.