Longest Common Substring

Medium20–25 min

Topics

Dynamic ProgrammingString

Companies

AmazonMicrosoftAdobe

Given two strings s1 and s2, find the length of their longest common substring — a run of characters that appears identically, and contiguously, in both strings. This looks close to the longest common *subsequence* problem, but one rule flips the whole approach: a subsequence can skip characters, so its DP table only ever grows or copies forward from a neighbor; a substring can't skip anything, so the moment two characters fail to match, whatever run was building there is completely over — the table entry resets to 0 instead of falling back on a neighbor's value. Tracking, for every pair of positions, "how long is the run that ends exactly here" turns every comparison into a single lookup, and the answer is just the largest number that ever shows up anywhere in that table.

Test Case 1:

Input:s1 = "geeksforgeeks", s2 = "geeksquiz"

Output:5

Explanation:Both strings start with the run "geeks" — five characters in a row that appear identically in both, and nothing longer lines up anywhere else.

Test Case 2:

Input:s1 = "abc", s2 = "def"

Output:0

Explanation:Not one character is shared between the two strings, so there's no common substring at all — not even length 1.

Test Case 3:

Input:s1 = "", s2 = "abc"

Output:0

Explanation:An empty string shares no run of characters with anything — the answer is 0 regardless of what s2 is.

Constraints

◆0 ≤ s1.length, s2.length ≤ 13
◆s1 and s2 consist of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Check Every Pair of Starting Positions

Brute

Anchor a starting position in s1 and a starting position in s2, then walk forward from both at the same time for as long as the characters keep matching — that run length is a valid common substring ending right there. Trying every possible pair of starting positions and keeping the longest run found covers every candidate substring, but the same characters can get re-walked many times across different starting pairs, since nothing is remembered between attempts.

TimeO(n² · m)

SpaceO(1)

Java

Try it out

class Solution {
    public int longestCommonSubstring(String s1, String s2) {
        int best = 0;
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                int len = 0;
                while (i + len < s1.length() && j + len < s2.length() && s1.charAt(i + len) == s2.charAt(j + len)) {
                    len++;
                }
                best = Math.max(best, len);
            }
        }
        return best;
    }
}

Optimal — DP: Run Length Ending at Each Cell

Optimal

Instead of re-walking a match from scratch at every starting pair, remember it: let dp[i][j] be the length of the common run that ends exactly at s1[i-1] and s2[j-1]. Whenever those two characters match, dp[i][j] is just one more than whatever run already ended right before them, at dp[i-1][j-1] — a single lookup instead of a fresh walk. When they don't match, no run can end there at all, so dp[i][j] stays 0 (this is what separates it from the longest-common-*subsequence* table, which never resets to 0 on a mismatch). The answer is simply the largest value that ever appears anywhere in the table.

TimeO(n · m)

SpaceO(n · m)