Longest common subsequence: keep order, allow gaps

The example has two equally good answers, AB and AC. A correct solver should not reject one merely because another was expected. It needs to find the best length and recover a sequence that really appears, in order, in both inputs.

What can be skipped?#

A subsequence keeps the original order but may leave characters out. It does not require adjacent characters. In the illustrative inputs ABC and ACB, AB is allowed because B appears after A in each string.

A longest common substring follows a stricter rule: its characters must be next to each other in both inputs. On these same two strings, no adjacent pair matches, so a longest common substring has length one. Permitting gaps changes the answer, not just the name.

Store the answer for each pair of prefixes#

A prefix is the beginning of a string: the first two characters of ABC are AB. Let dp[i][j] store the best shared-sequence length for the first i characters of a and the first j characters of b. Keeping answers to these smaller problems is dynamic programming.

Compare the final characters of the two prefixes. If they match, append that character to the answer for the two shorter prefixes. If they differ, at least one must be left out; keep the better of the two possibilities.

matching last characters: dp[i][j] = dp[i-1][j-1] + 1
different characters:    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Fill the table for ABC and ACB, then change the backtracking tie rule. AB and AC both have the best length. For a counterexample, enter ABC and XYZ: every interior cell stays zero. The mismatch rule preserves earlier matches only when some exist.

For a = ABC and b = ACB, the complete table is:

The cell for ABC and AC is 2: the two final C characters extend the length-1 result for AB and A. In the bottom-right cell, C and B differ. The cells above and to the left both contain 2, so the best length remains 2. A mismatch does not erase earlier matches.

def lcs(a: str, b: str) -> str:
    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])
    answer = []
    i, j = len(a), len(b)
    while i and j:
        if a[i - 1] == b[j - 1]:
            answer.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(answer))

Recover one sequence from the table#

Begin at the bottom-right cell. When the final characters match, record that character and move diagonally. Otherwise move to a neighbouring cell that preserves the best length.

For ABC and ACB, the code first moves upward at the tie. It then records B, skips the unmatched C in the second string, and records A. Those letters were collected backwards; reversing them returns AB. Choosing the other direction at the first tie could produce the equally valid AC.

For input lengths m and n, the table takes O(mn) time and space, including the stored smaller answers. Backtracking through it takes at most m+n moves. Empty input or inputs with no shared character return the empty string. These are correctness properties of the example, not measured performance claims.

0/1 knapsack uses the same idea of naming exactly what each table cell means, but its second dimension is remaining capacity rather than a second string. In either case, define the smaller question before writing the recurrence.

Memoization, rolling rows or Hirschberg?#

Choose what the caller needs before discarding the table. A length such as 2 is a different result from the actual sequence AB.

Memoization computes a smaller answer when first needed and saves it for later calls. This complete Python function evaluates the same prefix recurrence from the final pair backwards:

from functools import cache

def lcs_length_memo(a: str, b: str) -> int:
    @cache
    def length(i: int, j: int) -> int:
        if i == 0 or j == 0:
            return 0
        if a[i - 1] == b[j - 1]:
            return 1 + length(i - 1, j - 1)
        return max(length(i - 1, j), length(i, j - 1))

    return length(len(a), len(b))

The cache belongs to this invocation, so answers for different input strings are not mixed. In the worst case it still takes O(mn) time; recursion also has a depth limit. Python’s RecursionError guide explains why an iterative version is safer for a genuinely deep chain of calls. Raising the limit is not a memory optimisation.

For just the length, the iterative two-row version is:

def lcs_length_rows(a: str, b: str) -> int:
    if len(a) < len(b):
        a, b = b, a  # Keep the shorter string in the columns.
    previous = [0] * (len(b) + 1)
    for char_a in a:
        current = [0] * (len(b) + 1)
        for j, char_b in enumerate(b, 1):
            current[j] = (previous[j - 1] + 1 if char_a == char_b
                          else max(previous[j], current[j - 1]))
        previous = current
    return previous[-1]

It takes O(mn) time for non-empty inputs and O(min(m,n)+1) working space, including the empty-prefix cell. For ABC and ACB, it returns 2, not AB. It cannot follow the full-table backtracking code after those earlier rows have been thrown away.

Hirschberg’s original algorithm supplies the missing reconstruction. Split one input halfway; calculate prefix lengths forwards and suffix lengths backwards against the other input. Choose a crossing point with the best combined length, then solve the two smaller pairs and join their sequences. This keeps the O(mn) time bound while avoiding a full table. The original paper’s auxiliary-space bound is linear in one input; orienting the row calculations to the shorter input limits row storage. The returned sequence and recursion bookkeeping still need space. No Hirschberg implementation is claimed by the examples above.

Use the full table when a small input and an inspectable reconstruction matter. Use rolling rows when the length is enough. Consider Hirschberg when the sequence itself is required and a full table is too large. None of these choices guarantees a particular execution speed in a particular Python environment.