Longest Common Subsequence: The DP Grid Explained

The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both, in the same order, with gaps allowed. For night and eight it is ight. It is one of the standard two-string dynamic programming problems, and the grid it builds is the same grid behind edit distance and line-by-line diff tools.

The problem it solves

Given strings a and b, return the length of their LCS — and often the sequence itself. A subsequence keeps order but may skip characters: ace is a subsequence of abcde, while aec is not. That is different from a substring, which must be contiguous.

Why it matters: comparing two versions of a text is an LCS problem over lines. The lines outside the common subsequence are exactly the ones that were deleted or inserted. The number of single-character insertions and deletions needed to turn a into b is len(a) + len(b) - 2 × LCS.

Brute force is hopeless: a string of length m has 2ᵐ subsequences to check against the other string.

The intuition

Compare the last characters of the two strings.

• They match. Then that character can end the common subsequence. The answer is one more than the LCS of both strings with that last character removed.
• They differ. Then at least one of them is not the end of the LCS. So drop the last character of a, or drop the last character of b, and keep whichever gives the longer answer.

Every question here is about a prefix of a against a prefix of b. There are only (m + 1) × (n + 1) such pairs, so store each answer in a grid: grid[i][j] is the LCS length of the first i characters of a and the first j of b. Row 0 and column 0 are zero, because an empty string has nothing in common with anything. Every other cell looks at three neighbours: the diagonal (when the characters match), or the cell above and the cell to the left (when they do not).

Watch it run

The animation fills the grid for night against eight. Where the row's character matches the column's, the cell takes the diagonal plus one; elsewhere it copies the larger of its top and left neighbours. The last frames trace the diagonals back from the bottom-right corner and pick out the matched letters: ight, length 4.

The code

The grid, plus a walk back from the bottom-right corner that reads one LCS out of it:

def lcs(a, b):
    m, n = len(a), len(b)
    grid = [[0] * (n + 1) for _ in range(m + 1)]      # grid[i][j]: a[:i] vs b[:j]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                grid[i][j] = grid[i - 1][j - 1] + 1     # match: extend the diagonal
            else:
                grid[i][j] = max(grid[i - 1][j], grid[i][j - 1])   # drop one character
    out, i, j = [], m, n                                # walk back to read one LCS
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif grid[i - 1][j] >= grid[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return grid[m][n], "".join(reversed(out))

print(lcs("night", "eight"))                            # (4, 'ight')
print(lcs("ABCBDAB", "BDCABA"))                         # (4, 'BCBA')
print(lcs("abc", "xyz"))                                # (0, '')

The walk back mirrors the filling rule. On a match, the character is part of the answer and the walk steps diagonally. Otherwise it moves toward whichever neighbour holds the larger value, because that is where the cell's value came from. When both neighbours are equal, either direction is valid, and the choice decides which LCS you get when there are several: ABCBDAB and BDCABA also share BDAB and BCAB, all of length 4.

If you only need the length, each row depends only on the row above it, so two rows are enough. Putting the shorter string on the columns keeps the memory at O(min(m, n)):

def lcs_length(a, b):                                  # two rows are enough
    if len(b) > len(a):
        a, b = b, a
    prev = [0] * (len(b) + 1)
    for ch in a:
        cur = [0]
        for j, other in enumerate(b, 1):
            cur.append(prev[j - 1] + 1 if ch == other else max(prev[j], cur[j - 1]))
        prev = cur
    return prev[-1]

print(lcs_length("night", "eight"))                     # 4

To test both, a brute force tries subsets of positions in a, longest first, and returns the first one that is also a subsequence of b. The strings use a three-letter alphabet so that long common subsequences are frequent. The check also confirms that the string read back from the grid really is a subsequence of both inputs:

import itertools, random

def is_subsequence(s, t):
    it = iter(t)
    return all(ch in it for ch in s)                   # each match consumes t

def brute(a, b):                                       # longest subsequence of a found in b
    for k in range(len(a), -1, -1):
        for idx in itertools.combinations(range(len(a)), k):
            if is_subsequence("".join(a[i] for i in idx), b):
                return k

random.seed(9)
ok = True
for _ in range(2000):
    a = "".join(random.choice("abc") for _ in range(random.randint(0, 9)))
    b = "".join(random.choice("abc") for _ in range(random.randint(0, 9)))
    length, seq = lcs(a, b)
    ok &= length == brute(a, b) == lcs_length(a, b) == len(seq)
    ok &= is_subsequence(seq, a) and is_subsequence(seq, b)
print(ok)                                              # True

The is_subsequence helper uses a small Python trick: ch in it advances the iterator until it finds ch, so each character must be found after the previous one.

The complexity

The grid has (m + 1) × (n + 1) cells, each filled in O(1), so time is O(m · n). Space is O(m · n) for the full grid, which you need to read the sequence back, or O(min(m, n)) for the length alone. The walk back adds at most m + n steps. For two 10,000-character strings the grid holds a hundred million cells, which is one reason diff tools usually compare lines rather than characters.

Where it goes wrong

• Confusing subsequence with substring. Longest common substring resets to zero on a mismatch instead of taking the max of the neighbours. Mixing the two rules gives neither answer.
• Indexing the strings with the grid index. Cell i, j compares a[i - 1] and b[j - 1], because row 0 and column 0 are the empty prefixes.
• Throwing away the grid too early. The two-row version cannot recover the sequence; keep the full grid if you need it.
• Expecting a unique answer. Several subsequences can share the maximum length. If the problem wants a specific one, say the smallest in alphabetical order, the tie rule in the walk back has to follow it.

How to say it in an interview

"I compare prefixes. If the last characters match, the LCS is one plus the LCS of both shorter prefixes; otherwise it's the max of dropping the last character from either string. I store those answers in an (m + 1) × (n + 1) grid with a zero row and column, so it's O(m · n) time. To get the sequence I walk back from the bottom-right corner, stepping diagonally on matches. For the length alone, two rows are enough."

The same grid with a different cost rule is edit distance, and reading the answer back goes deeper into the walk-back step.