Overview
Longest Common Subsequence uses dynamic programming to compare prefixes and keep the best match length when characters either match or are skipped.
CoreSource checked
Longest Common Subsequence
Finds the longest sequence that appears in two inputs without requiring contiguous positions.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- Dynamic Programming
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
subsequencedynamic programmingprefix comparisonbacktracking
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n m)
Average
O(n m)
Worst
O(n m)
Space
O(n m)
When to Use
- Use when relative order matters but gaps are allowed.
- Use when diff tools is a central requirement.
When Not to Use
- Avoid when the match must be contiguous in both strings.
- Avoid when the distance or match rule does not reflect the real similarity question.
What It Does
- Compares two sequences
- Allows gaps
- Builds a dynamic programming table
Use Cases
- Diff tools
- DNA sequence comparison
- Version comparison
Inputs
- Two strings or sequences
Outputs
- Length or contents of a longest common subsequence
Key Formulas (1)
LCS recurrence
dp[i][j] = dp[i−1][j−1] + 1 if a[i] = b[j], else max(dp[i−1][j], dp[i][j−1])
dp[i][j] = dp[i-1][j-1] + 1 if a[i] == b[j], else max(dp[i-1][j], dp[i][j-1])Extends a match or skips one item from either sequence.
Pseudocode
- 1.Create a table for prefixes of both sequences
- 2.If the current items match, extend the diagonal value
- 3.Otherwise keep the larger value from left or above
- 4.Backtrack to recover a subsequence if needed
Canonical Example
- Input
- a = "ABCBD", b = "ACBD"
- Output
- LCS = "ACBD"
- Explanation
- All characters of ACBD appear in order in both strings.
Implementation Notes
- Use rolling rows if only the length is needed.
- Test exact match, no match, repeated characters, and empty input cases.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Confusing subsequence with substring changes the problem completely.
- Indexing and empty-pattern cases often cause off-by-one errors.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow a matrix where matching characters extend diagonal paths.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Create a table for prefixes of both sequences
sequence-matchNotes
A subsequence may skip characters; it is not the same as a substring.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Longest Common Subsequence invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborLongest Common Substring
Both compare shared sequence structure, but substring requires contiguity.
Conceptual neighborNeedleman-Wunsch
Both use dynamic programming on sequence pairs.
Related Algorithms
Tags
Pattern MatchingStringsDynamic ProgrammingSequence Alignment