LeetCode Visualizer
How it worksAll visualizations

Step by step · Python

Longest common subsequence, visualized

The longest common subsequence of two strings is the longest run of characters that appears in both in the same order, though not necessarily side by side. It is the idea underneath diff tools and DNA sequence alignment.

How it works
Python
a = "ABCBDAB"
b = "BDCABA"

dp = [[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]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[len(a)][len(b)])

How longest common subsequence works

dp[i][j] is the length of the LCS of the first i characters of a and the first j characters of b. If a[i − 1] equals b[j − 1], that character extends the best answer without either of them: dp[i − 1][j − 1] + 1. Otherwise at least one of the two characters is not in the answer, so take the larger of dp[i − 1][j] and dp[i][j − 1].

The example compares "ABCBDAB" and "BDCABA". Their longest common subsequence has length 4 — "BCBA" is one of them.

What to watch for when it runs

  1. A match reads the cell diagonally up and to the left; a mismatch reads the cell above or to the left.
  2. The grid has an extra row and column of zeros for the empty prefixes.
  3. The bottom-right cell is the answer.

Time and space complexity

Time
O(m × n)
Space
O(m × n)

m and n are the two string lengths. Keeping only two rows brings the memory down to O(n) if you only need the length.

Related visualizations

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.