Practice Longest Common Subsequence
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. A common subsequence of two strings is a subsequence that is common to both strings.
Source: Longest Common Subsequence on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
text1 = "abcde", text2 = "ace"
3
# Example 2
text1 = "abc", text2 = "abc"
3
# Example 3
text1 = "abc", text2 = "def"
0
Constraints
How to solve Longest Common Subsequence
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
The longest common subsequence of two prefixes is determined by whether their final characters match: if they do, extend the best answer for both prefixes shortened by one; if not, the best answer drops the last character of one string or the other. That optimal-substructure rule makes a two-dimensional table over prefix lengths the complete solution.
Why brute force is not enough
Enumerate every subsequence of one string, about 2^1000 of them at the maximum length, and test each for being a subsequence of the other in linear time. A recursion on index pairs is also exponential without memoization; adding memoization is exactly the dynamic program.
Approach
- Define a table where the entry at row i and column j holds the LCS length of the first i characters of text1 and the first j characters of text2; row 0 and column 0 are zero because an empty string shares nothing.
- Fill the table row by row. When the i-th character of text1 equals the j-th character of text2, the entry is the diagonal neighbor plus one, meaning both characters are consumed as a matched pair.
- When they differ, the entry is the maximum of the entry above, which drops a character of text1, and the entry to the left, which drops a character of text2. The invariant is that each entry is exact for its pair of prefixes.
- The bottom-right entry is the answer. To save memory, keep only the previous row and the current row, reading the diagonal value before it is overwritten.
Walkthrough of Example 1
text1 = "abcde", text2 = "ace" → 3
- Columns correspond to the prefixes of ace. Row for the prefix a of text1: a matches a giving 1, and the entries for ac and ace stay 1 because c and e do not match a.
- Row for ab: b matches nothing in ace, so each entry is the max of above and left, remaining 1, 1, 1.
- Row for abc: against a it is 1; against ac the c matches c, so take the diagonal entry 1 plus 1 for 2; against ace it stays 2. Row for abcd matches nothing and is 1, 2, 2.
- Row for abcde: against ace the e matches e, so take the diagonal entry for abcd versus ac, which is 2, plus 1 for 3.
- The bottom-right entry is 3, matching the expected output.
Time and space
Time O(mn) · Space O(min(m,n)). m and n are the lengths of text1 and text2; every table cell is computed once in constant time, and the rolling-row optimization keeps two rows of the shorter length, or O(mn) if the full table is stored.
Interview pitfalls
- Confusing subsequence with substring; characters may be skipped, so abc and ahbgdc share abc.
- Adding one in the mismatch case or taking the diagonal there as if a match occurred; only equal characters extend a subsequence.
- Off-by-one between table indices and string indices when the table has an extra zero row and column.
- In the one-row optimization, overwriting the diagonal value before it is read, which silently corrupts matched extensions.
Follow-up questions interviewers ask
- How would you reconstruct one actual longest common subsequence, and what changes if you need all of them?
- How does this relate to edit distance and to diff tools, and what changes in the recurrence?
Further reading on the technique: Longest common subsequence
Related LeetCode Problems
Practice more problems similar to Longest Common Subsequence.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.