Longest Common Substring

Longest Common Substring asks for the longest run of characters that appears, unbroken, in both strings. It looks almost identical to Longest Common Subsequence, but one word — contiguous — changes the whole recurrence.

The slow way first

The brute force: take every starting position in s1, every starting position in s2, and extend as long as the characters keep matching, tracking the longest run. That is O(m · n · min(m, n)) — for every pair of start points you might walk a whole substring. Far too slow for long strings.

The question to ask: while I am comparing one pair of characters, what do I wish I already knew? I wish I knew how long the matching run was that ended at the previous pair of characters. If I had that, I could extend it by one in O(1).

The idea: length of the run ending here

Let dp[i][j] be the length of the longest common substring that ends exactly at s1[i-1] and s2[j-1]. Then:

• If s1[i-1] == s2[j-1], this pair extends the diagonal run: dp[i][j] = dp[i-1][j-1] + 1.
• If they differ, the run is broken — a substring cannot have a gap — so dp[i][j] = 0.

The answer is the largest value anywhere in the grid, tracked in a running best. This is the key difference from Longest Common Subsequence, where you read the bottom-right corner.

The diagonal is doing all the work: a common substring shows up as a chain of cells going down-and-right, each one bigger than the last.

Walk through it

Step through the animation. We compare "abcde" against "abfce". When s1[0]='a' meets s2[0]='a', the cell becomes 1. The next diagonal cell, s1[1]='b' vs s2[1]='b', extends it to 2 — that is our best. Later matches like 'c' and 'e' light up too, but they sit alone (the cell before them on the diagonal was a mismatch, so they only reach 1). The running best ends at 2.

Pseudocode

dp = grid of zeros, size (m+1) x (n+1)
best = 0
for i from 1 to m:
    for j from 1 to n:
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1     # extend the diagonal run
            best = max(best, dp[i][j])      # remember the longest run so far
        else:
            dp[i][j] = 0                    # run is broken, reset
return best

The Python solution

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                best = max(best, dp[i][j])
            else:
                dp[i][j] = 0
    return best

• dp is an (m+1) x (n+1) grid; the extra row and column of zeros let us write dp[i-1][j-1] without a bounds check.
• best holds the longest run seen anywhere — we update it the instant a cell grows.
• The if branch is the diagonal extend: a match adds one to the run that ended at the previous pair.
• The else branch is the crucial difference from subsequence — a mismatch resets the cell to 0 because substrings must be contiguous.
• We return best, not dp[m][n] — the answer can sit anywhere in the grid.

Complexity

We trade O(m·n) extra space (the grid) to fill each cell in O(1). The space can be squeezed to O(n) by keeping only the previous row, since each cell looks only at its upper-left diagonal.

When this pattern shows up

Practice