Longest Common Subsequence
Problem Statement
Given two strings text1 and text2, return the length of their longest common subsequence. A common subsequence appears in both strings in the same relative order, but the chosen characters do not need to be contiguous.
Input
Two lowercase strings text1 and text2.
Output
An integer: the length of the longest subsequence common to both strings.
Constraints
- •
1 <= text1.length, text2.length <= 1000 - •
text1 and text2 consist of lowercase English letters
Examples
Example 1
text1 = abcde, text2 = ace
3Example 2
text1 = abc, text2 = abc
3Example 3
text1 = abc, text2 = def
0Learning Objectives
- Define a two-sequence DP state over prefixes of both strings.
- Separate the matching-character transition from the skip-one-character transition.
- Use an extra zero row and zero column to make empty-prefix base cases simple.
- Compress a 2D prefix table to one row without losing the diagonal dependency.
Intuition
Think about the last characters of two prefixes. If they match, there is no downside to pairing them: any common subsequence before those characters can be extended by one. That gives the diagonal transition.
If the last characters do not match, they cannot both be used as the final matched character. At least one of them must be skipped. The best answer is therefore the better of skipping the last character of text1 or skipping the last character of text2.
This is why LCS is the template for two-string DP: every cell represents a pair of prefixes, and each transition either consumes both strings together or consumes one side while keeping the other fixed.
Common mistakes
- ×Confusing subsequence with substring and requiring matched characters to be contiguous.
- ×Using indices directly without accounting for the empty prefix row and column.
- ×When characters differ, taking the diagonal value instead of the maximum of skipping one side.
- ×In the 1D optimization, overwriting the diagonal value before it is used.
- ×Trying to greedily match the first possible equal character, which can block a better later alignment.
State Definition
Let dp[i][j] be the length of the longest common subsequence between the first i characters of text1 and the first j characters of text2. The answer is dp[m][n], where m = text1.length and n = text2.length.
State Transition
Base cases are all empty-prefix cells: dp[0][j] = 0 and dp[i][0] = 0 because an empty string has no common characters with any prefix.
For i > 0 and j > 0:
If text1[i - 1] == text2[j - 1], then dp[i][j] = dp[i - 1][j - 1] + 1.
Otherwise, one last character must be skipped, so dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
Solutions
Solution 1: 2D prefix tabulation
Use this as the default interview solution. It is easiest to reason about, easiest to debug, and the full table can be reused if a follow-up asks you to reconstruct one LCS.
Build a table whose rows are prefixes of text1 and columns are prefixes of text2. The extra row and column represent empty prefixes. Fill the table from top-left to bottom-right so each cell can read its top, left, and diagonal dependencies.
Step-by-step
- Let m and n be the two string lengths.
- Create dp with m + 1 rows and n + 1 columns. Java initializes the empty-prefix base cases to zero.
- For every i from 1 to m and every j from 1 to n, compare the current characters.
- If they match, extend the diagonal value. Otherwise, take the better of the top and left cells.
- Return dp[m][n].
O(m · n)
O(m · n)
Every pair of prefix lengths is computed once.
Java implementation
Solution 2: 1D rolling row
Use this after presenting the 2D table when the interviewer asks for space optimization and only the length is needed. Keep the shorter string as columns to minimize memory.
Each row only needs the previous row and the current row's left value. A one-dimensional array stores the current best values by column, while a separate diagonal variable preserves the old dp[i - 1][j - 1] value before it is overwritten.
Step-by-step
- Put the shorter string on the columns so the array is as small as possible.
- Iterate through the longer string as rows.
- Before updating dp[j], save its old value as up because it becomes the next diagonal.
- On a match, write diagonal + 1. On a mismatch, write the max of the old dp[j] and the current dp[j - 1].
- Move diagonal to up at the end of the column step.
O(m · n)
O(min(m, n))
The same cells are evaluated, but only one row over the shorter string is stored.
Java implementation
Dry Run
Sample input
text1 = abcde, text2 = ace. Each row shows the full DP row against prefixes of ace, including the empty prefix column.
| i | text1 prefix | dp row for prefixes of ace | current best |
|---|---|---|---|
| 0 | empty | [0,0,0,0] | 0 |
| 1 | a | [0,1,1,1] | 1 |
| 2 | ab | [0,1,1,1] | 1 |
| 3 | abc | [0,1,2,2] | 2 |
| 4 | abcd | [0,1,2,2] | 2 |
| 5 | abcde | [0,1,2,3] | 3 |
The bottom-right value is 3, representing the matched sequence a, c, e.
Complexity Analysis
The full table and rolling-row forms both run in O(m · n). The optimized form reduces memory when reconstruction is not required.
2D prefix tabulation
O(m · n)
O(m · n)
Every pair of prefix lengths is computed once.
1D rolling row
O(m · n)
O(min(m, n))
The same cells are evaluated, but only one row over the shorter string is stored.
Interview Tips
Always define the state using prefix lengths rather than raw character indices; it makes the empty-prefix base cases natural. When explaining the mismatch case, say that the optimal answer must skip at least one of the two last characters, so the top and left cells cover all possibilities.
Likely follow-ups
- How would you reconstruct one actual longest common subsequence string?
- How would you compute the shortest common supersequence from the LCS table?
- How does the solution change for three strings?
- Can you reduce the space if you also need reconstruction?
Similar Problems
Key Takeaways
- Two-string DP usually means a grid over prefix lengths.
- A character match consumes both prefixes and extends the diagonal.
- A mismatch skips one side, so the transition takes max of top and left.
- Rolling rows require preserving the old diagonal before overwriting a cell.