Longest Common Subsequence

Definition

Longest Common Subsequence (LCS) is the problem of finding the longest sequence of elements that appears in the same relative order in two given sequences, without requiring the elements to be contiguous in either one.

Overview

A subsequence differs from a substring in that its elements don't need to be adjacent — only in the same relative order. For example, "ACE" is a subsequence of "ABCDE" even though characters are skipped between each match. The LCS problem asks, given two sequences, what is the longest subsequence they have in common, and it's a foundational example in the study of dynamic programming because its optimal substructure is unusually clean to state and prove. The standard solution builds a two-dimensional table where each cell (i, j) holds the length of the LCS of the first i characters of one string and the first j characters of the other. If the characters at positions i and j match, the cell's value is one more than the diagonal cell above-left, extending a shared subsequence; if they don't match, the cell takes the maximum of the cell above and the cell to the left, effectively trying "skip a character from string one" versus "skip a character from string two" and keeping whichever gives a longer result. This recurrence fills the table in O(m·n) time and space for strings of length m and n, and the actual subsequence (not just its length) can be reconstructed by tracing back through the table from the bottom-right corner. LCS underlies several widely used real-world tools: the `diff` utility and Git's line-by-line change detection are built on LCS-style algorithms that find the longest unchanged sequence of lines between two file versions, so that only the genuinely changed lines are reported as additions or deletions. Bioinformatics uses closely related algorithms to align DNA, RNA, and protein sequences and measure similarity between them. Because the straightforward O(m·n) space table can be reduced to O(min(m,n)) space when only the length (not the reconstructed subsequence) is needed, LCS is also a standard vehicle for teaching the general dynamic programming technique of space optimization by keeping only the current and previous rows of a DP table.

Key Concepts

• Finds the longest subsequence common to two sequences, preserving relative order
• Distinct from longest common substring, which requires contiguous characters
• Solved via a 2D dynamic programming table in O(m·n) time and space
• Recurrence extends a match diagonally or takes the max of skipping a character from either string
• Actual subsequence reconstructed by tracing back through the completed table
• Space can be optimized to O(min(m,n)) when only the length is needed
• Foundation of file diff tools like Unix diff and Git's change detection
• Closely related to sequence alignment algorithms used in bioinformatics

Use Cases

Frequently Asked Questions

Related in Computer Science