#1143 Longest Common Subsequence
the problem
In plain words
Return the length of the longest subsequence common to text1 and text2 (characters in order, gaps allowed). Return 0 if none.
in text1 = "abcde", text2 = "ace"
out 3
"ace".
in text1 = "abc", text2 = "abc"
out 3
in text1 = "abc", text2 = "def"
out 0
- 1 ≤ text1.length, text2.length ≤ 1000
- Lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern2D DP on two strings (LCS / edit distance)
where this runsUnix diff was built on this: Hunt and McIlroy's 1976 Bell Labs report describes diff as finding a longest common subsequence of lines.
Look at the last characters. If they match, they're part of an LCS: 1 + LCS of both shorter prefixes. If not, one of them must be dropped: max of the two options.
solutions
From brute force to optimal
lcs(i, j): match → 1 + lcs(i+1, j+1); else max(lcs(i+1, j), lcs(i, j+1)).
- Base: either string exhausted → 0.
- Branch on match / mismatch.
A mismatch branches twice; depth up to m + n.
Recursion depth.
class Solution { public int longestCommonSubsequence(String text1, String text2) { return lcs(text1, text2, 0, 0); } /** LCS of the suffixes text1[i..] and text2[j..]. */ private int lcs(String a, String b, int i, int j) { if (i == a.length() || j == b.length()) return 0; if (a.charAt(i) == b.charAt(j)) return 1 + lcs(a, b, i + 1, j + 1); return Math.max(lcs(a, b, i + 1, j), lcs(a, b, i, j + 1)); }}Only m × n (i, j) pairs exist.
- memo[i][j] = −1 initially.
- Check, compute, store.
Each pair once, O(1) work.
Memo + O(m + n) stack.
class Solution { public int longestCommonSubsequence(String text1, String text2) { int[][] memo = new int[text1.length()][text2.length()]; for (int[] row : memo) Arrays.fill(row, -1); return lcs(text1, text2, 0, 0, memo); } private int lcs(String a, String b, int i, int j, int[][] memo) { if (i == a.length() || j == b.length()) return 0; if (memo[i][j] != -1) return memo[i][j]; int result; if (a.charAt(i) == b.charAt(j)) result = 1 + lcs(a, b, i + 1, j + 1, memo); else result = Math.max(lcs(a, b, i + 1, j, memo), lcs(a, b, i, j + 1, memo)); return memo[i][j] = result; }}dp[i][j] = LCS of the first i chars and the first j chars.
- Row 0 / column 0 = 0 (empty prefix).
- Match → dp[i−1][j−1] + 1.
- Else → max(dp[i−1][j], dp[i][j−1]).
One O(1) step per cell.
The full table (needed if you must rebuild the string).
class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; // dp[i][j] = LCS of first i chars and first j chars for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; // match: extend the diagonal } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // drop a char from one side } } } return dp[m][n]; }}Fill the table, follow the arrows
Each row only reads the previous row → keep two rows of the shorter length.
- Make the shorter string the columns.
- Fill cur from prev; swap after each row.
Same cells.
Two rows of the shorter string's length.
class Solution { public int longestCommonSubsequence(String text1, String text2) { if (text1.length() < text2.length()) return longestCommonSubsequence(text2, text1); // shorter one = columns int n = text2.length(); int[] prev = new int[n + 1], cur = new int[n + 1]; // row i-1 and row i for (int i = 1; i <= text1.length(); i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { cur[j] = prev[j - 1] + 1; // match: diagonal + 1 } else { cur[j] = Math.max(prev[j], cur[j - 1]); // up or left } } int[] tmp = prev; prev = cur; cur = tmp; // the row we just filled becomes "previous" } return prev[n]; }}Two rows, swapped after each one
in the room
How to say it in the interview
talk track
- Define the state clearly: "dp[i][j] is the LCS of the first i letters of text1 and the first j of text2". Then the three neighbours explain themselves.
traps
- Mixing up
charAt(i)andcharAt(i − 1)with the +1-sized table. - Confusing subsequence with substring (Longest Common Substring resets to 0 on mismatch).
what they ask next
Follow-ups
Print the LCS itself?
Keep the full table; from (m, n) move diagonally on matches (record the char), otherwise toward the larger neighbour.
Shortest Common Supersequence (LC 1092)?
Length = m + n − LCS; rebuild by walking the same table.
before you submit
Edge cases to test
- No common letter → 0.
- Identical strings → their length.
- Subsequence, not substring: "axbxcxd" and "abcd" → 4.
practise next
Similar problems
- #72Edit DistanceMediumin Dynamic Programming
- #300Longest Increasing SubsequenceMediumin Dynamic Programming
- #5Longest Palindromic SubstringMediumin Dynamic Programming