AI engineering glossary · Data structures algorithms
What is LCS (longest common subsequence)?
Longest common subsequence (also called LCS): The longest sequence of items that appears in both of two sequences in the same order, though not necessarily side by side. It is solved by a dynamic programming table and underlies text comparison tools.
Longest common subsequence: an example
For 'ABCBDAB' and 'BDCABA', one longest common subsequence is 'BCBA' with length 4.
Related terms
More Data structures algorithms terms
- Longest increasing subsequence
- LRU cache
- Master theorem
- Memoization
- Merge sort
- Minimum spanning tree
- Monotonic stack
- NP-complete
Where you learn it
Longest common subsequence is part of the AI Engineering Program, which teaches it with notes, a hands-on lab and an exam. The first lesson is free.