Longest Common Subsequence
The longest common subsequence or LCS of two strings is the longest sequence of characters that appears in both, in the same relative order, though not necessarily contiguous. For ABCBDAB and BDCAB one answer is BCAB.
Dynamic programming
Compare the two strings character by character using a grid where one string runs along the rows and the other along the columns:
- If the current characters match, the LCS length grows by one over the diagonal cell.
- If they differ, take the larger of the cell above or the cell to the left.
The bottom right cell holds the final length. You recover the actual subsequence by tracing back through the choices.
Why it matters
LCS underlies file diff tools, version control merges, and DNA sequence alignment. A subsequence differs from a substring because a substring must be contiguous while a subsequence may skip characters.
Key idea
A grid comparing every prefix pair lets matches extend the diagonal while mismatches inherit the best neighbor.