How to Find the Longest Common Substring of Two Strings
Two strings go in. One shared, unbroken chunk comes out. That’s the longest common substring problem, and it powers plagiarism checkers, DNA comparison, and file diff tools as much as it haunts coding interviews.
Take “photograph” and “tomography.” The answer is “ograph”: six characters that appear in both, side by side, in the same order. This guide covers the definition, a dynamic programming solution in Python, the complexity, and faster options for huge inputs.
What Is the Longest Common Substring?
It’s the longest run of characters that appears in both strings, with no gaps. Contiguity is the whole point.
People mix it up with the longest common subsequence constantly. A subsequence can skip characters; a substring can’t. For “abcde” and “xbcdy,” the longest common substring is “bcd.”
| Substring | Subsequence | |
|---|---|---|
| Gaps allowed | No | Yes |
| Is “ace” shared with “abcde”? | No | Yes |
| Typical DP rule | Reset to 0 on mismatch | Carry the best neighbor value. |
Remember that last row. It’s the heart of the algorithm.
How the Dynamic Programming Solution Works
Build a grid where each cell dp[i][j] holds the length of the common ending shared by the first i characters of string A and the first j characters of string B. Two rules fill it:
- Characters match:
dp[i][j] = dp[i-1][j-1] + 1 - Characters differ:
dp[i][j] = 0
While filling, track the largest value and where it occurred. That position tells you where the answer ends.
Python
def longest_common_substring(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
best, end = 0, 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > best:
best, end = dp[i][j], i
return a[end - best:end]
print(longest_common_substring("photograph", "tomography")) # ographThe zero reset enforces contiguity. One mismatch breaks the chain, so the count starts over.
Time and Space Complexity
Two nested loops over lengths m and n give O(m × n) time. The full grid costs the same in space, but each row only reads the row above it, so two rows are enough. That drops memory to O(min(m, n)) if you keep the shorter string as the column dimension. Brute force, which compares every pair of starting positions and extends each match, runs around O(m × n × min(m, n)).
For huge inputs, a generalized suffix tree solves the problem in O(m + n) time, a result covered in Dan Gusfield’s Algorithms on Strings, Trees, and Sequences. A suffix automaton hits the same linear bound with simpler code. Both are overkill for most interviews, honestly, but name them if someone asks how to go faster.
Common Mistakes
Four traps catch most people:
- Returning the length when the question wants the string. Read the prompt twice.
- Skipping the zero reset. It quietly turns your solution into the subsequence problem.
- Slicing off by one. With a 1-indexed grid, the end index is
i, so the slice isa[end - best:end]. - Ignoring ties. Several substrings can share the maximum length, so ask which one to return.
Where It’s Used
Plagiarism detectors flag long shared passages. Bioinformatics tools compare DNA sequences. Version control systems and diff utilities find unchanged blocks between file versions.
FAQ: Longest Common Substring
Q: Is it the same as the longest common subsequence?
A: No. A substring must be contiguous, while a subsequence can skip characters. The DP rules differ accordingly.
Q: What’s the time complexity?
A: O(m × n) with dynamic programming, or O(m + n) with a suffix tree or suffix automaton.
Q: Can it work on more than two strings?
A: Yes. A generalized suffix tree handles many strings efficiently, while extending the DP grid gets expensive fast.
Q: Is there a LeetCode version?
A: Yes. Problem 718, “Maximum Length of Repeated Subarray,” is the same idea applied to arrays.
Q: Which language should I use?
A: Any. The grid logic is identical in Python, Java, C++, or JavaScript.
Wrapping Up
Match means add one to the diagonal. Mismatch means reset to zero. Track the maximum and slice the answer out. Master that pattern and you’ll also handle the subarray variants that show up in interviews. Next, compare it against the subsequence version to see how one changed rule alters the whole problem.
