AI Hints
Home›DSA in Python Tutorial›Dynamic Programming
DSA in Python · Lesson 93 of 132

Longest Common Subsequence

A two dimensional table.

⏱ 2 min read▶ Video at 1:51:04🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Longest Common Subsequence
From the video: Longest Common Subsequence
  • 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.

lcs.pypython
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"))
Output
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.

keyvalue
Rowsletters of the first
Columnsletters of the second
Cellanswer for the prefixes
CostO(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
Next up: The Knapsack Problem — best value that fits