Longest Common Substring

The longest common substring problem is solved by tracking, for every pair of positions (i, j), the length of a common run that ends exactly there — a match extends the diagonal run from (i-1, j-1) by one, and any mismatch collapses that run back to zero, because a substring must stay contiguous. The answer is simply the largest value that ever appears in that table.

Recognize the pattern

• The word is substring, not subsequence — characters must be contiguous in both strings.
• You need a length (or the actual run), not just an existence check.
• Two input strings, comparing all pairs of positions — smells like a 2D grid DP.
• Contrast with Longest Common Subsequence (LCS): that allows gaps and takes a max on mismatch; this resets to 0 on mismatch.

Brute force → optimal

Brute force: for every start index in s1 and every start index in s2, extend a comparison while characters match, tracking the best run. That's O(n) starts × O(m) starts × O(min(n,m)) extension ≈ O(n·m·min(n,m)) time, O(1) space. For n = m = 1000 that is up to ~10^9 character comparisons — too slow for a 1-second limit.

Optimal (DP): reuse work across overlapping extensions. If you already know the run ending at (i-1, j-1), extending by one matched character is O(1) instead of re-walking O(min(n,m)) characters. Same insight that powers LCS and edit distance: never re-measure a diagonal you've already measured.

Complexity, derived

Define dp[i][j] = length of the common substring ending at s1[i-1] and s2[j-1] (1-indexed, row/col 0 are base cases of value 0 for the empty prefix). Recurrence:

dp[i][j] = dp[i-1][j-1] + 1   if s1[i-1] == s2[j-1]
dp[i][j] = 0                  otherwise
answer   = max over all dp[i][j]

There are (n+1)(m+1) table cells and each is filled in O(1) from one neighbor, so time = O(n·m). The full table costs O(n·m) space; since each row only needs the previous row, that reduces to O(min(n,m)) space by keeping two rolling rows (or one row plus a diagonal-carry variable).

Worked example

s1 = "abdca", s2 = "cbda". Table rows are s1 characters (plus an empty-prefix row), columns are s2 characters (plus an empty-prefix column). Each cell is dp[i][j]:

The maximum value 2 occurs at row "d", column "d" — reading the matched diagonal backwards (b then d) gives the substring "bd", matching the expected output.

Java (O(n·m) time, O(min(n,m)) space)

public int longestCommonSubstring(String s1, String s2) {
    // keep the shorter string as columns to bound space by min(n, m)
    if (s1.length() < s2.length()) { String t = s1; s1 = s2; s2 = t; }
    int n = s1.length(), m = s2.length();
    int[] prev = new int[m + 1];
    int[] curr = new int[m + 1];
    int best = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                curr[j] = prev[j - 1] + 1;
                best = Math.max(best, curr[j]);
            } else {
                curr[j] = 0;
            }
        }
        int[] tmp = prev; prev = curr; curr = tmp;
    }
    return best;
}

Pitfalls

• Reusing LCS logic and taking max(dp[i-1][j], dp[i][j-1]) on mismatch — that silently turns this into Longest Common Subsequence and inflates the answer.
• Off-by-one indexing: dp is sized (n+1)×(m+1); s1.charAt(i-1), not s1.charAt(i).
• Tracking only the max value when the problem also wants the substring itself — you must additionally record the ending index (i) whenever best updates, then slice s1.substring(i-best, i).
• Rolling-array reuse without clearing: forgetting that curr[0] must stay 0 every row (it's never reset otherwise if you skip initialization).

When to use / when not

Use this O(n·m) DP whenever n, m are up to a few thousand and you need it fast to implement and easy to reason about. It also generalizes cleanly to reconstructing the actual substring and to k > 2 strings (with a k-dimensional table, at real cost).

Named alternative — Generalized Suffix Tree / Suffix Array with LCP: build a combined suffix structure over s1 + '#' + s2 + '$', then the longest common substring is read off from LCP values between suffixes from different source strings. A suffix automaton is built in genuinely O(n+m) time (O((n+m) log Σ) for a general alphabet). A suffix array is typically built in O((n+m) log(n+m)) with standard comparison-based sorting; the O(n+m) bound is only achievable with advanced linear-time construction algorithms (e.g. DC3/SA-IS), which are rarely the default teaching implementation. Either way this beats O(n·m) asymptotically and is the right call for very long strings (megabase genomic sequences) or repeated queries against a fixed string. The trade-off is implementation complexity: suffix arrays/automata are notably harder to build correctly and debug than a DP table, so for interview settings and moderate-size inputs the DP is the pragmatic default.

Takeaways

• Contiguity is the whole story: reset-to-0 on mismatch is what separates this from LCS.
• The DP cell answers "how long is the match ending here", not "is there a match somewhere before here" — that's why the global answer is a max over the whole table, not the bottom-right cell.
• Space collapses from O(n·m) to O(min(n,m)) because each row only reads the row above it.
• For very large inputs or repeated queries, a suffix-structure approach beats the DP asymptotically at the cost of implementation difficulty.

Recall

Why does mismatching reset dp[i][j] to 0 here, whereas Longest Common Subsequence takes max(dp[i-1][j], dp[i][j-1]) instead?

Pattern: interval/grid DP on two sequences, tracking a run that must end at the current position — the same family as Longest Common Subsequence, Edit Distance, and Maximum Square of 1s.