Longest Common Subsequence
Asked at Apple, Walmart
Problem
Given two strings, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. This is a classic 2D DP problem.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: generate all 2^m subsequences of text1 and check if each is a subsequence of text2. That's O(2^m * n) — exponential and too slow.
Key insight: use DP. Define dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1]. At each cell, either the characters match (take diagonal + 1) or they don't (take max of top or left).
The recurrence:
- If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
- Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Base case: dp[0][j] = 0 and dp[i][0] = 0.
Visual walkthrough for text1="abcde", text2="ace":
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3
Result: dp[5][3] = 3. LCS is "ace".
To reconstruct the actual subsequence (not just length), trace back from dp[m][n]. If characters match, include it and move diagonally. Otherwise, move toward the larger value (top or left).
Space optimization: since each row only depends on the previous row, you can reduce space from O(m*n) to O(min(m,n)) using two 1D arrays.
Optimal Approach
Create a 2D DP table of size (m+1) x (n+1) initialized to 0. Fill row by row:
- For i from 1 to m, for j from 1 to n:
- If
text1[i-1]==text2[j-1]:dp[i][j]=dp[i-1][j-1]+ 1 - Else:
dp[i][j]= max(dp[i-1][j],dp[i][j-1])
- If
- Return
dp[m][n].
Walkthrough with text1="abcde", text2="ace":
- i=1,j=1: a==a, dp[1][1] = dp[0][0]+1 = 1
- i=1,j=2: a!=c, dp[1][2] = max(dp[0][2],dp[1][1]) = 1
- i=2,j=1: b!=a, dp[2][1] = max(dp[1][1],dp[2][0]) = 1
- i=3,j=2: c==c, dp[3][2] = dp[2][1]+1 = 2
- i=5,j=3: e==e, dp[5][3] = dp[4][2]+1 = 3
Time: O(m*n). Space: O(m*n), reducible to O(min(m,n)).
What Trips People Up in Real Interviews
Confusing subsequence with substring. A subsequence does NOT need to be contiguous. "ace" is a subsequence of "abcde" but not a substring. The DP handles non-contiguous matches naturally.
Using dp[i][j] to represent the subsequence ending at i, j. That's wrong. dp[i][j] represents the LCS length of the first i characters of text1 and first j characters of text2. Think prefixes, not suffixes.
Off-by-one in the DP table. The table is (m+1) x (n+1) because index 0 represents the empty prefix. Access text1[i-1] when filling dp[i][j], not text1[i].
Forgetting to handle the case where characters don't match. If they don't match, take the max of the top cell and left cell. Don't set it to 0 — that would reset the count.
Not being able to reconstruct the actual LCS. To get the subsequence string, trace back from dp[m][n] diagonally when characters match, or move toward the larger value. This is a common follow-up.
Solution Code
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[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[m][n]Frequently Asked Questions
What is the Longest Common Subsequence problem?
Given two strings, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. This is a classic 2D DP problem.
How do you solve Longest Common Subsequence?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Common Subsequence?
Longest Common Subsequence is asked at Apple, Walmart. It is a medium difficulty problem.
What are common mistakes on Longest Common Subsequence?
- Confusing subsequence with substring. A subsequence does NOT need to be contiguous. "ace" is a subsequence of "abcde" but not a substring. The DP handles non-contiguous matches naturally.
- Using `dp[i][j]` to represent the subsequence ending at i, j. That's wrong. `dp[i][j]` represents the LCS length of the first i characters of text1 and first j characters of text2. Think prefixes, not suffixes.
- Off-by-one in the DP table. The table is (m+1) x (n+1) because index 0 represents the empty prefix. Access `text1[i-1]` when filling `dp[i][j]`, not `text1[i]`.
- Forgetting to handle the case where characters don't match. If they don't match, take the max of the top cell and left cell. Don't set it to 0 — that would reset the count.
- Not being able to reconstruct the actual LCS. To get the subsequence string, trace back from `dp[m][n]` diagonally when characters match, or move toward the larger value. This is a common follow-up.