Longest Common Substring

Medium
1603.

Longest Common Substring

Longest Common Substring is a medium coding problem on strings and dynamic programming, asked in Amazon, Microsoft and Morgan Stanley interviews.

Given two strings s1 and s2, return the length of the longest common substring — the longest string that appears in both as a block of consecutive characters.

This is different from the longest common subsequence: the characters of a substring must sit next to each other in both strings. The comparison is case-sensitive. If the strings share no character at all, the answer is 0.

Example 1

Input
s1 = "ABCDGH", s2 = "ACDGHR"
Output
4
Explanation
"CDGH" appears in both strings.

Example 2

Input
s1 = "abc", s2 = "acb"
Output
1
Explanation
No two-character block is shared, but single letters are.

Example 3

Input
s1 = "YZ", s2 = "yz"
Output
0
Explanation
Upper- and lowercase letters are different characters.

Constraints

  • 1 <= s1.length, s2.length <= 1000
  • s1 and s2 consist of English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var longestCommonSubstr = function(s1, s2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Common Substring — Solution in Python, Java & C++

Longest Common Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Common Substring is a medium coding problem on strings and dynamic programming, asked in Amazon, Microsoft and Morgan Stanley interviews.

Problem statement

Given two strings s1 and s2, return the length of the longest common substring — the longest string that appears in both as a block of consecutive characters.

This is different from the longest common subsequence: the characters of a substring must sit next to each other in both strings. The comparison is case-sensitive. If the strings share no character at all, the answer is 0.

Example 1

Input: s1 = "ABCDGH", s2 = "ACDGHR"
Output: 4
Explanation: "CDGH" appears in both strings.

Example 2

Input: s1 = "abc", s2 = "acb"
Output: 1
Explanation: No two-character block is shared, but single letters are.

Example 3

Input: s1 = "YZ", s2 = "yz"
Output: 0
Explanation: Upper- and lowercase letters are different characters.

Constraints

  • 1 <= s1.length, s2.length <= 1000
  • s1 and s2 consist of English letters

Hints for Longest Common Substring

  1. Hint 1

    A common substring ends at some position i of s1 and some position j of s2. How long can it be if it ends exactly there?

  2. Hint 2

    Let len[i][j] be the length of the longest common block ending at s1[i - 1] and s2[j - 1]. If those characters differ it is 0; otherwise it extends the block ending one step earlier in both.

  3. Hint 3

    The answer is the largest len[i][j] anywhere — not the bottom-right cell. Only the previous row is needed, so two 1-D arrays suffice.

How to solve Longest Common Substring

Fix where the common block ends: at index i in s1 and j in s2. If the characters there match, the block is one longer than the block ending at i - 1, j - 1; if they don't, no common block ends there at all. The best end pair gives the answer.

Approach

  1. Keep prev and cur, both of length m + 1 (m = s2.length), zero-filled.
  2. For each i from 1 to n, for each j from 1 to m: cur[j] = prev[j - 1] + 1 if s1[i - 1] == s2[j - 1], else 0. Track the maximum.
  3. Swap prev and cur after each row (resetting cur[0] = 0). Return the maximum seen.

Why it works

A block of length L ending at (i, j) means the last L characters before and including those positions agree pairwise; that holds exactly when the characters at (i, j) agree and a block of length L - 1 ends at (i - 1, j - 1). So len[i][j] is computed correctly from the previous row, and every common substring is counted at its own end pair.

Complexity

  • Time — O(n * m)
  • Space — O(m)

Pitfalls

  • Unlike the subsequence DP there is no max(left, up) carry-over — a mismatch resets the run to 0.
  • The answer is the maximum over the whole table, not the last cell.
  • With a single rolling array, iterate j downward or you read the current row's value instead of the previous one.

Reference solution

Python

def longestCommonSubstr(s1: str, s2: str) -> int:
    m = len(s2)
    prev = [0] * (m + 1)
    best = 0
    for ch in s1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == s2[j - 1]:
                v = prev[j - 1] + 1
                cur[j] = v
                if v > best:
                    best = v
        prev = cur
    return best

Java

public static int longestCommonSubstr(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[] prev = new int[m + 1], cur = new int[m + 1];
    int best = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cur[j] = s1.charAt(i - 1) == s2.charAt(j - 1) ? prev[j - 1] + 1 : 0;
            if (cur[j] > best) best = cur[j];
        }
        int[] t = prev; prev = cur; cur = t;
    }
    return best;
}

C++

int longestCommonSubstr(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    int best = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cur[j] = s1[i - 1] == s2[j - 1] ? prev[j - 1] + 1 : 0;
            best = max(best, cur[j]);
        }
        swap(prev, cur);
    }
    return best;
}

JavaScript

var longestCommonSubstr = function(s1, s2) {
    var n = s1.length, m = s2.length;
    var prev = new Array(m + 1).fill(0);
    var cur = new Array(m + 1).fill(0);
    var best = 0;
    for (var i = 1; i <= n; i++) {
        for (var j = 1; j <= m; j++) {
            cur[j] = s1.charCodeAt(i - 1) === s2.charCodeAt(j - 1) ? prev[j - 1] + 1 : 0;
            if (cur[j] > best) best = cur[j];
        }
        var t = prev; prev = cur; cur = t;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming