Introduction
A subsequence is a sequence you can derive from another by deleting zero or more elements without changing the order of remaining elements. For example, "ACE" is a subsequence of "ABCDE".
The Longest Common Subsequence (LCS) problem asks: given two strings, find the longest subsequence present in both.
For strings "ABCDE" and "ACE", the LCS is "ACE" with length .
You'll encounter LCS in:
- Diff tools: Git uses LCS to show file changes
- Bioinformatics: Comparing DNA sequences
- Spell checkers: Measuring string similarity
Intuition
Let's trace through strings "ABCD" and "AEBD".
You start by comparing characters from the end. If the last characters match, they must be part of the LCS. If they don't, you try two options: skip one character from the first string, or skip one from the second.
Compare 'D' and 'D'. They match. Include 'D' in the LCS. Now solve for "ABC" and "AEB".
Compare 'C' and 'B'. They don't match. You check both: LCS("AB", "AEB") and LCS("ABC", "AE"). Take the longer result.