1143. Longest Common Subsequence
Asked at Apple, Walmart, Visa
Difficulty
Medium
Time
O(m * n)
Space
O(m * n), reducible to O(min(m,
Pattern
String
Companies
3
Problem
You are given two strings, text1 and text2. Return the length of their longest common subsequence.
A subsequence of a string is what you get by deleting some characters (possibly none) while keeping the remaining characters in their original order. The characters do not need to be next to each other. For example, "ace" is a subsequence of "abcde".
A common subsequence is a string that is a subsequence of both inputs. You only need to return the length of the longest such string. If the two strings share no common subsequence at all, return 0.
A subsequence keeps order, not adjacency
Constraints
- ●
1 <= text1.length, text2.length <= 1000 - ●
text1 and text2 consist of only lowercase English characters
Examples
text1 = "abcde", text2 = "ace"3text1 = "abc", text2 = "abc"3text1 = "abc", text2 = "def"0Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Walmart | Medium | View all Walmart questions → |
| Visa | Medium | View all Visa 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.
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)).
Fill the DP table row by row
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
O(m * n) timedef 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 runs in O(m * n) time and O(m * n), reducible to O(min(m, space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Longest Common Subsequence?
Longest Common Subsequence is asked at Apple, Walmart, Visa. 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.