Longest Common Subsequence: The DP Family Behind Edit Distance

TL;DR: When a problem hands you two sequences and asks you to compare, align, or transform one into the other, you are in the LCS family. The recurrence is two lines: if the current characters match, take the diagonal cell and add one; if they do not, take the better of dropping a character from either side. Edit Distance, Delete Operation for Two Strings, Shortest Common Supersequence, and Longest Common Substring are all that same grid with a different rule in the mismatch branch. The count of sequences in the problem statement is the tell, and one word in it, subsequence or substring, decides two lines of your code.

This is the seventeenth deep dive in our pattern series (the full map lives in the hub), following 0/1 knapsack, and it is the second of two on dynamic programming. The six DP families are mapped in the dynamic programming guide; this post goes deep on the one that guide lists fourth, and which produces more interview questions than any other DP family because every string comparison problem lands here.

The tell: how to recognize an LCS problem

The tell is countable. Two sequences arrive, and the question relates them:

• "the longest common subsequence / substring"
• "edit distance", "minimum operations to convert one into the other"
• "minimum deletions or insertions to make them equal"
• "is s3 an interleaving of s1 and s2"
• "how many distinct subsequences of s equal t"
• "the shortest string containing both as subsequences"

Compare that against the neighbouring families. One sequence with a best-ending-here flavour is Longest Increasing Subsequence. One sequence read from both ends is Palindromic Subsequence, though that one is really this family applied to a string and its own reverse. Items against a budget is 0/1 knapsack. Counting the sequences first is the fastest triage step in all of dynamic programming.

The one insight the whole pattern rests on

Here is the sentence that is the pattern: index the table by a prefix of each sequence, and decide only the last character.

Let dp[i][j] be the answer for the first i characters of a and the first j characters of b. There are only two situations, and each one reduces to a smaller pair of prefixes:

if a[i-1] == b[j-1]:  dp[i][j] = dp[i-1][j-1] + 1        # match: consume both
else:                 dp[i][j] = max(dp[i-1][j],         # drop a's last character
                                     dp[i][j-1])         # drop b's last character

The matching case is the easy one: if the last characters agree, they can both be part of the answer, so take whatever the shorter prefixes achieved and add one. The mismatch case is where the family's variations live: at least one of the two characters cannot be used, so you try discarding each in turn and keep the better result.

Everything else in this family is that grid with a different mismatch rule. That is the sentence to carry into an interview.

The template

def longest_common_subsequence(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]        # row 0 and column 0 = empty prefix

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:                  # note the -1: table is 1-based
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

The extra row and column are what remove the boundary special cases. dp[0][j] means "compare an empty string against the first j characters", which is zero, and having those cells already present means the loop body never needs an if i == 0 branch. This is the same device as the leading zero in a prefix sum array, and it pays off the same way.

The consequence is the indexing offset that causes most bugs here: the table is 1-based while the strings are 0-based, so the character corresponding to dp[i][j] is a[i-1], never a[i]. Write the -1 deliberately rather than discovering it through a failing test.

Edit Distance: the same grid, three choices

Edit Distance is where candidates think a new algorithm has arrived. It has not. The table is identical and only the mismatch branch changes, from two options to three:

def min_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i                                   # delete every character of a
    for j in range(m + 1):
        dp[0][j] = j                                   # insert every character of b

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]            # free, no operation needed
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],   # replace
                                   dp[i - 1][j],       # delete from a
                                   dp[i][j - 1])       # insert into a
    return dp[n][m]

Two differences from LCS, both worth stating out loud. The base row and column are no longer zeros: turning a prefix of length i into an empty string costs i deletions, so the boundary carries real values. And the three-way minimum corresponds exactly to the three edit operations, with the diagonal being replace, up being delete, and left being insert. Once you can point at each cell and name its operation, the problem is finished.

Subsequence or substring: the word that changes the code

This is the distinction the family is built to test, and it is worth being precise. A subsequence may skip characters; a substring must be contiguous. "ace" is a subsequence of "abcde" and not a substring of it.

For Longest Common Substring, three things change:

1. The mismatch branch resets to zero rather than taking a maximum, because a break in the run ends it.
2. The answer is the maximum value anywhere in the table, not the bottom-right corner, because the best run may end anywhere.
3. You therefore track a running best while filling the table.

def longest_common_substring(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                best = max(best, dp[i][j])             # the answer can end anywhere
            else:
                dp[i][j] = 0                           # the run is broken
    return best

Three changes, one family. If you can explain why the reset and the roaming answer travel together, you understand the pattern rather than the problem.

Want the whole family taught in order? The two-sequence dynamic programming chapters of Grokking the Coding Interview build from LCS through Edit Distance and the palindromic variants with worked table traces and code in six languages, then do the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Longest Common Subsequence: the template, asked directly.
• Longest Common Substring: the reset-to-zero variant.
• Edit Distance: the three-way minimum. One of the most asked DP questions anywhere.
• Delete Operation for Two Strings: the answer is n + m - 2 × LCS, which you can derive in one line rather than writing a new table.
• Minimum ASCII Delete Sum for Two Strings: the same shape with character values instead of counts, which checks whether you generalize or memorize.
• Shortest Common Supersequence: length is n + m - LCS, and reconstructing the actual string means walking the table backwards. Reconstruction is a common follow-up across this whole family.
• Distinct Subsequences: counting rather than maximizing, so the match branch adds two terms instead of taking a maximum.
• Interleaving String: two sequences consumed into a third, so the table is indexed by how much of each has been used.
• Uncrossed Lines: LCS with the wording changed entirely. A good final check on whether you recognize the family by structure rather than by keywords.

The three mistakes that sink candidates

1. Confusing subsequence with substring. Read the word in the problem statement and write down which one it is before touching the table. The mismatch branch and the location of the answer both depend on it.

2. Wrong base row and column in Edit Distance. Leaving them as zeros is the LCS habit carried over, and it silently claims that converting a five-character string into an empty one is free. They must be i and j.

3. Index confusion between the table and the strings. The table runs from 0 to n while the string runs from 0 to n-1, so the comparison is always a[i-1] against b[j-1]. Getting this wrong usually produces an answer that is off by a small amount rather than an obvious crash, which makes it slow to find.

On space optimization

Each row depends only on the row above it, so the table reduces to two rows, or to one row plus a saved diagonal value. It is a reasonable follow-up and it is worth practising once. It is not worth attempting first: get the full 2D version correct and explained, then reduce it if asked. The 2D table is also far easier to reconstruct an answer from, and reconstruction is asked more often than space reduction.

Practice ladder

In order, each rung adding one wrinkle.

1. Longest Common Subsequence (M): the template and the offset.
2. Longest Common Substring (M): reset to zero, track the running best.
3. Edit Distance (M): the three-way minimum and the real base cases.
4. Delete Operation for Two Strings (M): derive it from LCS rather than rebuilding.
5. Minimum ASCII Delete Sum (M): generalize counts to weights.
6. Shortest Common Supersequence (H): reconstruct by walking the table backwards.
7. Distinct Subsequences (H): counting instead of maximizing.
8. Interleaving String (M): two sequences feeding a third.
9. Stretch: Uncrossed Lines (M), recognizing the family with every keyword removed.

Then write the tell in your own words ("I should suspect the LCS family when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One tell you can count (two sequences), one table indexed by a prefix of each, one recurrence with two branches (match takes the diagonal plus one, mismatch takes the better of dropping either side), one device that removes the boundary cases (an extra row and column), and one word in the problem statement that changes two lines (subsequence or substring). Edit Distance is the same grid with three choices, and half the family reduces to LCS with a one-line formula. The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: Tree DFS, where the value you return to your parent and the value you track globally are two different things.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential DP problems in its 6-week plan.

FAQs

What is the longest common subsequence problem? Given two sequences, find the longest ordered set of characters that appears in both, without requiring those characters to be adjacent. The standard solution fills a table indexed by prefixes of the two inputs, taking the diagonal plus one on a match and the better of two neighbours on a mismatch.

What is the difference between a subsequence and a substring? A subsequence may skip characters as long as the order is preserved, while a substring must be a contiguous block. That difference changes the mismatch branch from taking a maximum to resetting to zero, and moves the answer from the bottom-right cell to the largest value anywhere in the table.

How is Edit Distance related to LCS? It is the same table with a different mismatch rule. Instead of choosing between dropping a character from either string, you take the cheapest of replace, delete, and insert, which are the diagonal, upper, and left neighbours. The base row and column also hold real costs rather than zeros.

Why does the table have n+1 rows and m+1 columns? So that row zero and column zero can represent an empty prefix. Having those cells present means the main loop never needs a special case for the first character, which removes the most common source of off-by-one errors in this family.

Is the LCS family asked at FAANG companies? Frequently. Edit Distance and Longest Common Subsequence are standard at Google and Amazon, Interleaving String and Distinct Subsequences appear as harder follow-ups, and Uncrossed Lines shows up as a test of whether a candidate recognizes the structure when the vocabulary is unfamiliar.