Longest Common Substring

The problem, simply

You get two words. Find the longest piece that sits inside both of them, letter for letter, with no gaps. Give back its length.

A piece with no gaps is called a substring. This is different from a subsequence, where you may skip letters. Here, one wrong letter in the middle breaks the piece.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every pair of starting spots, one in each word. From each pair, walk forward with two fingers while the letters keep matching. Remember the longest walk.

1. For every i in the first word and every j in the second word:
2. Set len = 0. While both fingers are inside their words and s1[i + len] == s2[j + len], add 1 to len.
3. Keep the biggest len you ever see.

class Solution {
    public int longestCommonSubstring(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int best = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = 0;
                // walk both fingers forward while the letters match
                while (i + len < m && j + len < n
                        && s1.charAt(i + len) == s2.charAt(j + len)) {
                    len++;
                }
                best = Math.max(best, len);
            }
        }
        return best;
    }
}

How long it takes: m * n starting pairs, and each walk is at most as long as the shorter word, O(m * n * min(m, n)). Extra room: a few counters, O(1).

Way 2: the clever way

The walks in Way 1 repeat work. The walk from (2, 1) checks C, D, G, H. The walk from (3, 2) checks D, G, H again. Instead, flip it around: for each pair of letters, ask how long the matching piece is that ends right here. That only needs the answer for the pair just before, which sits one step up and to the left in a table.

1. Make a table dp with one extra row and column of zeros.
2. If s1[i - 1] == s2[j - 1], then dp[i][j] = dp[i - 1][j - 1] + 1. The chain grows by one.
3. Otherwise dp[i][j] = 0. The chain breaks.
4. The answer is the biggest number anywhere in the table, not the bottom right box.

class Solution {
    public int longestCommonSubstring(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        int best = 0, endInS1 = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;   // the chain grows
                    if (dp[i][j] > best) {
                        best = dp[i][j];
                        endInS1 = i;                    // remember where it ends
                    }
                } else {
                    dp[i][j] = 0;                       // the chain breaks
                }
            }
        }
        // s1.substring(endInS1 - best, endInS1) is the piece itself
        return best;
    }
}

How long it takes: one quick step per box, O(m * n). Extra room: the table, O(m * n). Each box only looks at the row above, so you can keep just two rows, or even one row filled from right to left, for O(n) room.

Watch out for

• On a mismatch the box is 0. Copying the max of up and left turns this into the subsequence problem and gives a wrong, bigger answer.
• If you need the piece itself, remember the row where the best chain ends, then cut s1.substring(end - best, end).
• With one row and a left to right loop, you overwrite the corner before you read it. Go right to left, or keep the old corner in a variable.
• Empty words: the loops never run and the answer stays 0.

What interviewers ask next

• Return the substring, not the length. Remember the end index next to the best length, as in the code.
• Can it be faster? Yes. A suffix automaton or a suffix array of s1 + '#' + s2 gives O(m + n). Binary search on the length with rolling hashes gives about O((m + n) log(min(m, n))).
• Longest repeated substring in one word: same table with a word against itself, but skip the boxes where i == j. Suffix arrays are the grown-up tool.
• Longest common substring of many words: binary search the length and check each word's hashes, or build a generalized suffix tree.
• What changes if gaps are allowed? It becomes longest common subsequence: on a mismatch, copy the bigger of up and left instead of writing 0.

Remember this

Grown-up words: the bead stretch is the longest common substring, the chart is the DP table, growing from the corner is the diagonal recurrence, and "ends right here" is the usual trick of defining the state by where the answer ends.