How Do You Find the Longest Common Substring?
Learn the longest common substring dynamic programming approach, how it differs from LCS, and how to answer this interview question.
Expected Interview Answer
The longest common substring is the longest contiguous block of characters that appears identically in both strings, found with a 2D dynamic programming table in O(m*n) time where a match resets a run counter and any mismatch resets it to zero, unlike the longest common subsequence which allows gaps.
Define dp[i][j] as the length of the common substring ending exactly at A[i-1] and B[j-1]. If A[i-1] equals B[j-1], dp[i][j] = dp[i-1][j-1] + 1, extending the run that ended just before these characters. If they differ, dp[i][j] must be exactly 0, because a substring cannot skip characters — any mismatch breaks contiguity entirely, unlike LCS which would take the max of neighbors. The answer is not dp[m][n] but the maximum value seen anywhere in the table, since the longest common run can end at any position, not necessarily at the end of both strings.
- Detects exact contiguous overlaps between texts
- Useful for plagiarism detection and DNA motif finding
- O(m*n) time with straightforward table filling
- Can be optimized to O(min(m,n)) space with a rolling row
AI Mentor Explanation
Two independent commentary transcripts of the same over occasionally use identical back-to-back phrasing, and the goal is to find the longest unbroken run of words both transcripts share verbatim in a row. Every time the next word in both transcripts matches, the current unbroken run grows by one word; the instant a word differs, that particular run ends completely and must restart from zero, not just pause. Unlike hunting for scattered shared words anywhere in the transcript, this only cares about one continuous stretch of identical wording. Tracking the longest such stretch across every possible starting point is what the substring table computes.
Step-by-Step Explanation
Step 1
Build a 2D table
Create dp of size (m+1) x (n+1), all zero, tracking match-run length ending at each cell.
Step 2
Match extends the run
If A[i-1] == B[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
Step 3
Mismatch resets to zero
If characters differ, dp[i][j] = 0 — unlike LCS, there is no carrying forward a max.
Step 4
Track the global maximum
The answer is the largest dp value seen anywhere in the table, along with its ending index for reconstruction.
What Interviewer Expects
- Contrast the reset-to-zero rule with LCS taking max(dp[i-1][j], dp[i][j-1])
- State the answer is the table maximum, not dp[m][n]
- Give O(m*n) time complexity and mention the O(min(m,n)) space optimization
- Explain how to reconstruct the actual substring from the max cell position
Common Mistakes
- Confusing longest common substring with longest common subsequence and applying the wrong recurrence
- Reading the answer as dp[m][n] instead of the table-wide maximum
- Forgetting a mismatch resets the run to exactly 0, not the max of neighbors
- Not tracking the ending index needed to reconstruct the actual substring
Best Answer (HR Friendly)
“Longest common substring finds the longest unbroken chunk that two strings share, versus longest common subsequence which allows gaps. I build a grid where a match extends a run by one, but any mismatch resets that run all the way to zero, and the answer is the biggest run I ever saw anywhere in the grid, not just the corner cell.”
Code Example
def longest_common_substring(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
best_len, end_index = 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_len:
best_len = dp[i][j]
end_index = i
else:
dp[i][j] = 0
return a[end_index - best_len:end_index]Follow-up Questions
- How does longest common substring differ from longest common subsequence in the recurrence?
- How would you optimize the space to O(min(m, n))?
- How would you solve this using a generalized suffix tree instead of DP?
- How would you find the longest common substring across more than two strings?
MCQ Practice
1. What happens to dp[i][j] when A[i-1] and B[j-1] do not match, in the longest common substring DP?
A mismatch breaks contiguity entirely, so the run length resets to exactly 0, unlike LCS which carries a max forward.
2. Where is the final answer for longest common substring found in the DP table?
Since the longest matching run can end at any position, the answer is the overall maximum value in the table, not the bottom-right cell.
3. What is the key structural difference between longest common substring and longest common subsequence?
A substring must be an unbroken contiguous block, while a subsequence can skip characters while preserving order.
Flash Cards
What is the DP recurrence when characters match in longest common substring? — dp[i][j] = dp[i-1][j-1] + 1, extending the run ending just before.
What happens on a mismatch? — dp[i][j] resets to exactly 0, breaking the contiguous run entirely.
Where is the answer read from in the DP table? — The maximum value found anywhere in the table, not the bottom-right cell.
How does substring differ from subsequence structurally? — A substring must be contiguous; a subsequence may skip characters while preserving order.