Longest Common Subsequence
On this page
Problem statement
Given two strings
text1andtext2, return the length of their longest common subsequence, or 0 if they share no characters. A subsequence keeps the original order of characters but may skip any of them:"one"is a subsequence of"stone", while"eno"is not.
The classic two-string DP. It is the backbone of diff, version-control merges and DNA alignment, and the same table shape solves Edit Distance and many string questions after it. Original problem: LeetCode 1143.
Example

Input: text1 = "stone", text2 = "longest"
Output: 3 # "one"
Input: text1 = "abcd", text2 = "bcda"
Output: 3 # "bcd"
Input: text1 = "abc", text2 = "def"
Output: 0
Constraints (assumed)
- 1 ≤ length of each string ≤ 1,000.
- Lowercase English letters.
What this question tests
- Defining a 2D state over prefixes and the two-case recurrence (letters equal / not equal).
- Seeing why a greedy match fails, which is the reason DP is needed.
- Optimising memory to two rows and reconstructing the subsequence itself.
Questions to ask first
- Subsequence or substring? A substring must be contiguous and uses a different recurrence. (Here: subsequence.)
- Do you want the length or the subsequence itself? (Here: length; the string is a follow-up.)
- How long can the strings be? O(n · m) time is fine up to a few thousand each.
- Is the comparison case-sensitive? (Here: lowercase only.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.