☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Longest common substring

Hard TUF ID 309 A2Z

Java source ↗ Edit this article ↗

Problem

Given two strings s1 and s2, return the length of the longest string that appears as a contiguous block (a substring) in both. Unlike a subsequence, a substring cannot skip characters. If no character is shared, the answer is 0.

Constraints: 1 ≤ n, m ≤ 1000 in the usual version; the Java methods also accept empty strings. The same problem on integer arrays is LeetCode 718, “Maximum Length of Repeated Subarray”, and every method below carries over unchanged.

Example 1

s1 = "abcjklp", s2 = "acjkp"
answer = 3          // "cjk" appears in both

Example 2

s1 = "abcde", s2 = "ace"
answer = 1          // the longest common subsequence "ace" has length 3, but no two shared characters are adjacent in both

Approach 1: Brute force

Intuition. A common substring is fixed by where it starts in each string. For every pair of start positions (i, j), extend forward while the characters agree; the length reached is the longest common block starting there. The best over all pairs is the answer.

Algorithm.

  1. For every i in s1 and every j in s2:
  2. Let len = 0; while both i + len and j + len are in range and s1[i + len] == s2[j + len], increase len.
  3. Keep the maximum len.
static int bruteForce(String s1, String s2) {
    int n = s1.length(), m = s2.length(), best = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int len = 0;
            while (i + len < n && j + len < m && s1.charAt(i + len) == s2.charAt(j + len)) len++;
            best = Math.max(best, len);
        }
    }
    return best;
}

Complexity. Time O(n · m · min(n, m)): n · m start pairs, each extended up to min(n, m) steps. On two strings of 1000 equal letters that is over 3 × 10^8 character comparisons. Space O(1).

The waste is visible: the pair (i, j) extends over exactly the same characters as the pair (i + 1, j + 1), minus one. Each block is re-measured from every one of its starting points.

Approach 2: Tabulation

Intuition. Fix where the block ends instead of where it starts. Let dp[i][j] be the length of the longest common block ending exactly at s1[i - 1] and s2[j - 1], using prefix lengths so row 0 and column 0 are the empty base case.

This is where it departs from LCS. In LCS a mismatch takes max(up, left) because a subsequence may skip a character and keep going. A substring may not, so a mismatch resets the count. And because the best block can end anywhere, the answer is the maximum over the whole table, not the bottom-right cell.

Algorithm.

  1. Create dp[n + 1][m + 1] (all zeros) and best = 0.
  2. For i = 1 .. n, j = 1 .. m: on a match set dp[i][j] = 1 + dp[i - 1][j - 1] and update best; otherwise set it to 0.
  3. Return best.
static int tabulation(String s1, String s2) {
    int n = s1.length(), m = s2.length(), best = 0;
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];             // extend the block that ended one step earlier
                best = Math.max(best, dp[i][j]);
            } else {
                dp[i][j] = 0;                                // a mismatch breaks every block ending here
            }
        }
    }
    return best;
}

Dry run on s1 = "abab" (rows), s2 = "bab" (columns):

  ”” b a b
”” 0 0 0 0
a 0 0 1 0
b 0 1 0 2
a 0 0 2 0
b 0 1 0 3

Non-zero values only grow along diagonals, and every mismatch drops to 0. The maximum, 3, is the block "bab" ending at the last characters of both strings. In this case it happens to be the corner cell, but in Example 1 the corner holds only 1 (the final p of both strings) while the maximum 3 sits in the middle.

Complexity. Time O(n · m), space O(n · m).

Approach 3: Space optimized

Intuition. Each cell reads only its upper-left neighbour, which lives in the previous row. Keep two rows and swap them. One detail matters more here than in LCS: the mismatch branch must explicitly write 0. After a swap, cur holds the row from two steps ago, and a stale non-zero value left there would be read as a block that does not exist.

Algorithm.

  1. prev and cur of length m + 1, best = 0.
  2. For each i, fill cur[1..m] (match: 1 + prev[j - 1], mismatch: 0), then swap.
  3. Return best.
static int spaceOptimized(String s1, String s2) {
    int n = s1.length(), m = s2.length(), best = 0;
    int[] prev = new int[m + 1], cur = new int[m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                cur[j] = 1 + prev[j - 1];
                best = Math.max(best, cur[j]);
            } else {
                cur[j] = 0;                                  // must be reset: the array holds an older row
            }
        }
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    return best;
}

Complexity. Time O(n · m), space O(m).

Approach 4: Diagonal scan, constant space

Intuition. The table above shows that dp[i][j] depends only on dp[i - 1][j - 1], the previous cell on the same diagonal. Different diagonals never interact. A diagonal is the set of pairs where j - i is fixed, that is, it compares s1[i] with s2[i + shift] for one fixed shift. Along a diagonal the problem becomes “longest run of consecutive matches”, which needs a single counter.

shift ranges from -(n - 1) (only s1’s last character against s2’s first) to m - 1 (the reverse). For each shift, i starts at max(0, -shift) so that i + shift is never negative.

Algorithm.

  1. For each shift from -(n - 1) to m - 1, set run = 0.
  2. Walk i along the diagonal: run = run + 1 on a match, 0 otherwise; update best.
  3. Return best.
static int diagonalScan(String s1, String s2) {
    int n = s1.length(), m = s2.length(), best = 0;
    for (int shift = -(n - 1); shift <= m - 1; shift++) {    // compare s1[i] with s2[i + shift]
        int run = 0;
        for (int i = Math.max(0, -shift); i < n && i + shift < m; i++) {
            run = s1.charAt(i) == s2.charAt(i + shift) ? run + 1 : 0;
            best = Math.max(best, run);
        }
    }
    return best;
}

Dry run of the diagonal that holds the answer in Example 1, shift = -1 (compare s1[i] with s2[i - 1]):

i s1[i] s2[i - 1] run best
1 b a 0 0
2 c c 1 1
3 j j 2 2
4 k k 3 3
5 l p 0 3

Complexity. Time O(n · m): the diagonals together cover every pair (i, j) exactly once. Space O(1).

For much longer strings, a suffix automaton or binary search with rolling hashes reaches O((n + m) log(n + m)) or better, but those are beyond what this sheet expects.

Edge cases and pitfalls