How Do You Find the Longest Common Subsequence?
Learn the longest common subsequence dynamic programming solution, its recurrence, complexity, and how to answer this interview question.
Expected Interview Answer
The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both strings in the same relative order but not necessarily contiguously, found with a 2D dynamic programming table in O(m*n) time and O(m*n) space.
Define dp[i][j] as the LCS length of the first i characters of string A and the first j characters of string B. If A[i-1] equals B[j-1], the matching character extends the best subsequence found without either character, so dp[i][j] = dp[i-1][j-1] + 1. Otherwise the characters cannot both be used together, so dp[i][j] takes the best of skipping one character from either string: max(dp[i-1][j], dp[i][j-1]). The final answer sits in dp[m][n], and backtracking through the table from that cell recovers the actual subsequence, not just its length.
- Solves diff tools and version comparison
- Foundation for edit distance and sequence alignment
- O(m*n) time is efficient for typical string sizes
- Backtracking recovers the actual matching sequence
AI Mentor Explanation
Two scorers each write down the order of batsmen dismissed during a match, but from different vantage points, occasionally missing a name. Finding the LCS means finding the longest list of batsmen both scorers agree were dismissed, in the same order, even if other names appear only in one scorer's list. When both scorers' next name matches, that batsman extends the shared list; when they differ, the analyst checks whether dropping the next name from either scorer's list gives a longer shared sequence. Building this comparison one name at a time, cell by cell, is exactly how the LCS table grows to the full agreed dismissal order.
Step-by-Step Explanation
Step 1
Build a 2D table
Create dp of size (m+1) x (n+1), initialized to zero for empty-prefix base cases.
Step 2
Match extends diagonally
If A[i-1] == B[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
Step 3
Mismatch takes the best skip
Otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Step 4
Read off and backtrack
dp[m][n] is the LCS length; walk backward through the table to reconstruct the actual subsequence.
What Interviewer Expects
- Correctly define the dp[i][j] recurrence including both cases
- State O(m*n) time and O(m*n) space complexity
- Explain how to reconstruct the actual subsequence via backtracking
- Mention the O(min(m,n)) space optimization using rolling rows
Common Mistakes
- Confusing subsequence (non-contiguous) with substring (contiguous)
- Forgetting to initialize the base row/column to zero
- Off-by-one errors indexing A[i-1]/B[j-1] against dp[i][j]
- Not knowing how to backtrack to recover the actual sequence, only the length
Best Answer (HR Friendly)
“LCS finds the longest sequence of characters two strings share in the same order, even if they're not sitting next to each other. I build a grid where each cell asks 'do these two characters match', and either extend a previous match or carry forward the better of two neighboring options, which is exactly how tools like git diff spot what changed between versions.”
Code Example
def longest_common_subsequence(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
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])
# Backtrack to reconstruct the actual subsequence
i, j, seq = m, n, []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
seq.append(a[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return dp[m][n], "".join(reversed(seq))Follow-up Questions
- How would you reduce the space complexity to O(min(m, n))?
- How does LCS relate to computing edit distance?
- How would you find the LCS of three strings instead of two?
- How would you print all possible longest common subsequences, not just one?
MCQ Practice
1. What is the time complexity of the standard LCS dynamic programming solution for strings of length m and n?
Filling an (m+1) x (n+1) table with O(1) work per cell gives O(m * n) total time.
2. When characters A[i-1] and B[j-1] do not match, what is dp[i][j]?
On a mismatch, the best result comes from skipping one character in either string, so we take the max of the two neighboring subproblems.
3. Which best describes a subsequence used in LCS?
A subsequence keeps the original relative order of characters but allows gaps, unlike a substring which must be contiguous.
Flash Cards
What does dp[i][j] represent in the LCS table? — The length of the LCS between the first i characters of A and the first j characters of B.
What is the LCS recurrence when characters match? — dp[i][j] = dp[i-1][j-1] + 1.
What is the time complexity of LCS? — O(m * n), where m and n are the two string lengths.
Name one real-world application of LCS. — Diff tools comparing file versions (also DNA sequence alignment).