Longest Common Subsequence
Problem
text1 and text2, return the length of
the longest string that is a subsequence of both (characters kept in their original
order, but not necessarily adjacent). Return 0 if they share no
character."abcde", "ace"Output3 ("ace")"abc", "abc"Output3"abc", "def"Output01 ≤ text1.length, text2.length ≤ 1000 · lowercase English letters only
Try it yourself
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
}
}
1 + lcs(i-1, j-1)); if not, one of them is useless, so take
max(lcs(i-1, j), lcs(i, j-1)). Only (m+1)(n+1) distinct
prefix pairs exist.Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].
Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.
Open the String DP guide →Approaches
Brute ForcePlain Recursion on Prefixes
O(2m+n)Space O(m + n)lcs(i, j) = LCS of the first i and j
characters. On a mismatch it branches twice, and each branch shrinks
i + j by only one, so the call tree can have ~2m+n nodes
— the same (i, j) pairs are solved over and over.
public int longestCommonSubsequence(String text1, String text2) { return lcs(text1, text2, text1.length(), text2.length()); } private int lcs(String a, String b, int i, int j) { if (i == 0 || j == 0) return 0; if (a.charAt(i - 1) == b.charAt(j - 1)) return 1 + lcs(a, b, i - 1, j - 1); return Math.max(lcs(a, b, i - 1, j), lcs(a, b, i, j - 1)); }
Captures the recurrence perfectly, but exponential; hopeless beyond ~20 chars.
Better2-D Tabulation (Bottom-Up)
O(m·n)Space O(m·n)Fill dp[i][j] for all prefix pairs in increasing order, so each
cell's three dependencies (top, left, top-left) are ready. Row 0 and column 0 are
0 (empty prefix). Memoizing the recursion gives the same bounds.
public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) dp[i][j] = text1.charAt(i - 1) == text2.charAt(j - 1) ? 1 + dp[i - 1][j - 1] : Math.max(dp[i - 1][j], dp[i][j - 1]); return dp[m][n]; }
Polynomial and stack-safe; the full table also lets you rebuild the LCS string.
Optimal1-D Rolling Row
O(m·n)Space O(min(m, n))Row i only reads row i-1. Keep one array over the
shorter string: before overwriting, dp[j] is “above”,
dp[j-1] is “left”, and the saved old
dp[j-1] (diag) is “top-left”.
public int longestCommonSubsequence(String text1, String text2) { if (text2.length() > text1.length()) return longestCommonSubsequence(text2, text1); int m = text1.length(), n = text2.length(); int[] dp = new int[n + 1]; for (int i = 1; i <= m; i++) { int diag = 0; // dp[i-1][j-1] for (int j = 1; j <= n; j++) { int above = dp[j]; dp[j] = text1.charAt(i - 1) == text2.charAt(j - 1) ? diag + 1 : Math.max(above, dp[j - 1]); diag = above; } } return dp[n]; }
Dry run"abcde" vs "ace" — dp[0..3]
- 'a'0111a = a → diag+1
- 'b'0111no match → same
- 'c'0122c = c → 1+1
- 'd'0122no match → same
- 'e'0123e = e → 3 ✔
Same time, memory reduced to the shorter string's length.
(m, n): diagonal on a match, else toward the larger neighbour.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion on Prefixes | O(2m+n) | O(m + n) |
| Better | 2-D Tabulation (Bottom-Up) | O(m·n) | O(m·n) |
| Optimal | 1-D Rolling Row | O(m·n) | O(min(m, n)) |
- Confusing subsequence with substring — mismatches must not reset to 0.
- Off-by-one:
dp[i][j]usescharAt(i-1),charAt(j-1). - Rolling array without saving
diag— top-left gets overwritten.
- Write the recurrence first, then point out the overlapping
(i, j)states. - Show the progression recursion → memo/table → one row.
- LCS is the template for Edit Distance and Delete Operations for Two Strings.