Longest Common Subsequence
A two dimensional table.
How similar are two pieces of text? One way to measure it is the longest common subsequence. The longest set of letters that appear in both, in the same order, but not necessarily side by side. It's how diff tools and DNA comparisons work.

- How similar are two strings?
- Same order, gaps allowed
- Diff tools and DNA
Filling a grid
We make a grid, with one row for each letter of the first word, and one column for each letter of the second. If two letters match, the answer is one more than the cell diagonally up and left. If they don't, we take the better of the cell above, and the cell to the left. The bottom right cell is the answer. Run it. Abcde and ace share three letters, A, C, and E.
def lcs(a, b):
grid = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
grid[i][j] = grid[i - 1][j - 1] + 1
else:
grid[i][j] = max(grid[i - 1][j], grid[i][j - 1])
return grid[-1][-1]
print(lcs("abcde", "ace"))
print(lcs("kitten", "sitting"))3 4
Two dimensional DP
When a problem involves two strings, or two lists, the table usually becomes a grid. Each cell answers the problem for a beginning of each one. Filling it takes O of N times M, the product of the lengths. Edit distance, used by spell checkers, works exactly the same way.
| key | value |
|---|---|
| Rows | letters of the first |
| Columns | letters of the second |
| Cell | answer for the prefixes |
| Cost | O(n × m) |
Summary
The longest common subsequence fills a grid, matching letters diagonally, and otherwise taking the best neighbour. Next, the famous knapsack problem.
Key takeaways- Match: diagonal + 1
- No match: max of neighbours
- Answer: bottom right