Longest Common Subsequence
Problem statement
Given two strings text1 and text2, return the length of their longest common subsequence: the longest sequence of characters that appears in both strings in the same order, though not necessarily contiguously. Return 0 if they share no characters.
This is the core of how diff decides which lines two versions of a file have in common; everything outside the common subsequence is shown as an insertion or a deletion.
Examples
Example 1
Input: text1 = "deploy", text2 = "delay"
Output: 4
Explanation: "dely" appears in both, in order.
Example 2
Input: text1 = "abc", text2 = "xyz"
Output: 0
Explanation: No character is shared.
Hints
Approach
Two rows. Each row of the table only reads the row above it, so keep just prev and cur. Make the shorter string the column dimension so the rows are as short as possible. After each row, swap them. Memory drops to O(min(m, n)), though you lose the ability to reconstruct the subsequence from the table.
O(m · n)Space O(min(m, n))def longest_common_subsequence(text1, text2): if len(text2) > len(text1): text1, text2 = text2, text1 prev = [0] * (len(text2) + 1) for ch in text1: cur = [0] * (len(text2) + 1) for j in range(1, len(text2) + 1): if ch == text2[j - 1]: cur[j] = prev[j - 1] + 1 else: cur[j] = max(prev[j], cur[j - 1]) prev = cur return prev[-1] print(longest_common_subsequence("deploy", "delay"))print(longest_common_subsequence("abc", "xyz"))Follow-up questions
- Print one actual longest common subsequence by walking back through the full table.
- Output a line-level diff (lines marked kept, added or removed) for two short files.
Frequently asked questions
Diffing is everyday infra work: config drift between environments, terraform plan style comparisons, reviewing changed manifests. LCS is the classic algorithm underneath line-based diff, so it is a natural DP question with a real use, and it is the base for Edit Distance.
If both last characters are equal, some longest common subsequence ends with that character matched to it. Any solution that doesn't use it can swap its last matched pair for this one without getting shorter, so 1 + lcs(i-1, j-1) is always optimal in that case.
Not for large files, since O(m · n) memory is too much. Tools such as GNU diff and git use Myers' algorithm, which finds a shortest edit script in time proportional to the input size times the number of differences, and is fast when the files are mostly alike.