Start practising

Longest Common Substring

Medium Dynamic Programming Strings Original on GeeksforGeeks

Longest Common Substring is a medium dynamic programming problem solved with the strings pattern. The best approach, optimal (dp ending at each pair, one row), runs in O(m · n) time and O(n) space. Below are 2 approaches in Java, from brute force up.

Problem

Return the length of the longest common substring (contiguous) of two strings.

Examples

Example 1

Input
s1 = "ABCDGH", s2 = "ACDGHR"
Output
4
Why
"CDGH".

Example 2

Input
s1 = "abc", s2 = "acb"
Output
1

Constraints

  • 1 <= length <= 1000.
  • Unlike a subsequence, a substring must be contiguous.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute forceO(m · n · min(m, n))O(1)
Optimal (DP ending at each pair, one row)O(m · n)O(n)

1Brute force

TimeO(m · n · min(m, n))
SpaceO(1)

For every pair of start positions, extend while the characters match.

  1. For i, j: k = 0; while s1[i + k] == s2[j + k]: k++; track the max.
Java
class Solution {
    public int longestCommonSubstr(String s1, String s2) {
        int best = 0;
        for (int i = 0; i < s1.length(); i++)
            for (int j = 0; j < s2.length(); j++) {
                int k = 0;
                while (i + k < s1.length() && j + k < s2.length() && s1.charAt(i + k) == s2.charAt(j + k)) k++;
                best = Math.max(best, k);
            }
        return best;
    }
}

2Optimal (DP ending at each pair, one row)

TimeO(m · n)
SpaceO(n)

Match: dp[i][j] = dp[i - 1][j - 1] + 1; mismatch: 0. Track the running maximum. With one row, loop j backwards so dp[j - 1] still holds the previous row's value.

  1. For i, for j from n down to 1: dp[j] = match ? dp[j - 1] + 1 : 0; best = max.
Java
class Solution {
    public int longestCommonSubstr(String s1, String s2) {
        int n = s2.length(), best = 0;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= s1.length(); i++)
            for (int j = n; j >= 1; j--) {
                dp[j] = s1.charAt(i - 1) == s2.charAt(j - 1) ? dp[j - 1] + 1 : 0;
                best = Math.max(best, dp[j]);
            }
        return best;
    }
}

Edge cases to test

  • No common character (0)

Hints

Hint 1

dp[i][j] = length of the common substring ending exactly at s1[i - 1] and s2[j - 1]. A mismatch resets it to 0. The answer is the maximum cell, not the last one.

FAQ

What is the best time complexity for Longest Common Substring?

Optimal (DP ending at each pair, one row) runs in O(m · n) time and O(n) extra space.

Which pattern does Longest Common Substring use?

It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.

Is there a brute force solution for Longest Common Substring?

Yes. Brute force takes O(m · n · min(m, n)) time and O(1) space. For every pair of start positions, extend while the characters match.

Which edge cases should I test for Longest Common Substring?

No common character (0).