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.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Microsoft, Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1000s1 and s2 consist of English letters
Hints for Longest Common Substring
Hint 1
A common substring ends at some position
iofs1and some positionjofs2. How long can it be if it ends exactly there?Hint 2
Let
len[i][j]be the length of the longest common block ending ats1[i - 1]ands2[j - 1]. If those characters differ it is0; otherwise it extends the block ending one step earlier in both.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
- Keep
prevandcur, both of lengthm + 1(m = s2.length), zero-filled. - For each
ifrom 1 ton, for eachjfrom 1 tom:cur[j] = prev[j - 1] + 1ifs1[i - 1] == s2[j - 1], else0. Track the maximum. - Swap
prevandcurafter each row (resettingcur[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 to0. - The answer is the maximum over the whole table, not the last cell.
- With a single rolling array, iterate
jdownward 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 bestJava
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