LCSLongest common subsequence

01Why it exists

Reach for it when you see:Two sequences, the part they share, relative order preserved but gaps allowed, diff, alignment, fewest deletions and insertions, similarity, dp[i][j] over two prefixes.

02The core idea

A subsequence is what you get by deleting any number of elements and keeping the rest in their original order — no requirement that they be adjacent. The longest common subsequence (LCS) of A and B is the longest sequence that is a subsequence of both. Brute force means listing all 2ᵐ subsequences of A and checking each, which is hopeless. The DP state is defined over two prefixes: dp[i][j] is the LCS length of "the first i elements of A" and "the first j elements of B". The table is (m+1) × (n+1), row 0 and column 0 stand for the empty sequence and are all zeros, and the answer sits in the bottom-right cell dp[m][n].

The transition looks only at the last element of each prefix. If A[i−1] = B[j−1], then some longest LCS ends with that character: even if a given LCS does not use this pair, swapping its last character for this pair is still valid and just as long. So dp[i][j] = dp[i−1][j−1] + 1. If the two differ, they cannot both be the last character of the LCS, so at least one of them goes unused — dropping A's gives dp[i−1][j], dropping B's gives dp[i][j−1], and you take the larger. Every cell depends only on the cells above, to the left and diagonally up-left, so filling row by row, left to right guarantees that everything it reads is already computed.

The complexity is m×n cells at O(1) each, so O(mn) time. For space: rebuilding the LCS itself requires keeping the whole table, O(mn), walking back from the bottom-right, taking the character and moving diagonally on a match and moving towards the larger value otherwise. If you only need the length, each row uses only the row above, so rolling two rows brings it down to O(min(m, n)). Two 10,000-character texts make a hundred million cells, which is fine for time but several hundred megabytes for the full table — that is when you switch to Hirschberg's divide-and-conquer method, which reconstructs the answer in linear space.

Common traps. Confusing a subsequence with a substring: the longest common substring requires contiguity, so the transition becomes dp[i−1][j−1] + 1 on a match and 0 otherwise, and the answer is the maximum over the whole table rather than the bottom-right cell. Off-by-one indexing: row i of dp corresponds to A[i−1]. And assuming the LCS is unique: on a tie, going up or going left gives different answers of the same length. As for the neighbouring lessons — if only deletions and insertions are allowed, turning A into B takes m + n − 2·LCS steps, and adding substitution gives you Edit Distance in the next lesson, filled in exactly the same way. And as the LIS lesson mentions, when one of the two sequences has no repeated elements, LCS converts into LIS and can be solved in O(n log n).

03The algorithm

1. 1Create a (m+1) × (n+1) table dp, with row 0 and column 0 all zeros — the LCS against an empty sequence.
2. 2Fill it cell by cell for i from 1 to m and j from 1 to n: if A[i−1] == B[j−1] then dp[i][j] = dp[i−1][j−1] + 1, otherwise take max(dp[i−1][j], dp[i][j−1]).
3. 3The bottom-right cell dp[m][n] is the LCS length.
4. 4To rebuild the LCS: start at (m, n), and when the characters match, take that character and move diagonally up-left; when they differ, move up or left towards the larger dp value, breaking ties either way. Reverse what you collected for the answer. Along the way, moving up deletes a character of A and moving left inserts a character of B — that is the diff.
5. 5If you only need the length, roll two rows instead, with the shorter sequence as the row width, bringing the space down to O(min(m, n)).

04Interactive demo

A = PYTHON, B = TYPHOON. P, Y and T appear in opposite order on the two sides, so there is more than one LCS. The table fills row by row: blue is the cell being filled, yellow are the cells it reads — the diagonal neighbour when the characters match, the cells above and to the left when they differ — and the small arrow in each cell's top-left corner records where its answer came from (ties always record ←). Then the backtrack runs from the bottom-right: green outlines mark the path and solid green marks the characters that belong to the LCS. The diff grows underneath at the same time, with green for kept, a yellow − for deleted from A and a blue + for inserted from B. This path yields THON, and the last step lists the two other answers you would get by breaking the ties the other way, all of length 4.

05Code

The Python tab has the full table, the reconstruction of the LCS string, and a line-by-line diff whose sample output looks just like git diff. The C++ tab has the string reconstruction, which needs the whole table, and the space-saving two-row version for when you only need the length. Both languages break ties towards the left when backtracking, so they land on the same answer as the interactive demo.

def lcs_table(a, b):
    """dp[i][j]: the LCS length of a's first i elements and b's first j. O(mn)"""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]   # row 0 and column 0 are the empty sequence: all zeros
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # match: extend the LCS with both of them removed
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # differ: at least one of them is dropped
    return dp


def lcs_string(a, b):
    """Walk back from the bottom-right along the sources to rebuild one LCS (ties go left, as in the demo)"""
    dp = lcs_table(a, b)
    i, j, out = len(a), len(b), []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i][j - 1] >= dp[i - 1][j]:
            j -= 1
        else:
            i -= 1
    return "".join(reversed(out))


def diff(old, new):
    """Line by line: lines in the LCS are unchanged, the rest are deletions (-) or additions (+)"""
    dp = lcs_table(old, new)
    i, j, out = len(old), len(new), []
    while i > 0 or j > 0:
        if i > 0 and j > 0 and old[i - 1] == new[j - 1]:
            out.append("  " + old[i - 1]); i -= 1; j -= 1
        elif j > 0 and (i == 0 or dp[i][j - 1] >= dp[i - 1][j]):
            out.append("+ " + new[j - 1]); j -= 1
        else:
            out.append("- " + old[i - 1]); i -= 1
    return out[::-1]


if __name__ == "__main__":
    print(lcs_table("PYTHON", "TYPHOON")[-1][-1], lcs_string("PYTHON", "TYPHOON"))   # 4 THON
    old = ["import os", "x = 1", "print(x)", "return x"]
    new = ["import os", "import sys", "x = 2", "print(x)", "return x"]
    print("\n".join(diff(old, new)))
    #   import os
    # - x = 1
    # + import sys
    # + x = 2
    #   print(x)
    #   return x

06Practice

• LeetCode 1143Longest Common SubsequenceMedium
• LeetCode 1035Uncrossed Lines (lines that do not cross means order is preserved: LCS in disguise)Medium
• LeetCode 583Delete Operation for Two Strings (the answer is m + n − 2·LCS)Medium
• LeetCode 718Maximum Length of Repeated Subarray (contrast: requiring contiguity makes it a substring)Medium
• LeetCode 712Minimum ASCII Delete Sum for Two Strings (swap "length" for a sum of character values)Medium
• LeetCode 1092Shortest Common Supersequence (build the LCS table, then emit both sides along the path)Hard