Definition
- Longest Common Substring – finds the longest contiguous block of characters that appears in both strings.
- DP cell meaning –
dp[i][j]is the length of the common substring ending exactly at positionA[i-1]andB[j-1]. - Match rule – if
A[i-1] == B[j-1], thendp[i][j] = dp[i-1][j-1] + 1, extending the contiguous run. - Mismatch rule – if characters differ,
dp[i][j] = 0because the contiguous run is broken. - Answer location – the global maximum over all cells, not the bottom-right corner as in LCS.
A log-forensics tool at the National Bank of India compares two server request logs to find the longest identical contiguous block, which might indicate a replayed request. When the current characters match, the shared run grows by one. The instant they differ, the run resets to zero because contiguity is broken.
Understanding the Concepts
What is the Longest Common Substring problem?
The Longest Common Substring problem asks for the longest contiguous block of characters that appears in both strings. Unlike the Longest Common Subsequence, which allows gaps, a substring must be a continuous stretch. For example, for "TRANSFER" and "TRANSFORM", the longest common substring is "TRANS" with length 5.
package com.bank.core;
// String A: "TRANSFER"
// String B: "TRANSFORM"
// Common substrings: "T", "TR", "TRA", "TRAN", "TRANS", "R", "AN", ...
// Longest: "TRANS" with length 5
How does the DP table differ from LCS?
The crucial difference is what dp[i][j] represents. In LCS, dp[i][j] is the best LCS length up to prefixes of length i and j. In Longest Common Substring, dp[i][j] is the length of the common run ending exactly at those two positions. This means the cell only has a nonzero value if the characters at those positions match and extend a run from the diagonal.
package com.bank.core;
// LCS dp[i][j]: best subsequence length for prefixes i and j
// Substring dp[i][j]: length of common run ENDING at A[i-1] and B[j-1]
// LCS mismatch: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
// Substring mismatch: dp[i][j] = 0 (run is broken)
// LCS answer: dp[m][n] (bottom-right corner)
// Substring answer: max over ALL cells in the table
How do you implement it?
You build a table of size (m+1) x (n+1) with a zero border. You fill it row by row, and on each match you extend the diagonal by one. On each mismatch you set the cell to zero. You track a running maximum over all cells as you fill them.
package com.bank.service;
public class LongestCommonSubstring {
public int findLength(String a, String b) {
int m = a.length();
int n = b.length();
int[][] dp = new int[m + 1][n + 1];
int maxLen = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = Math.max(maxLen, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return maxLen;
}
public static void main(String[] args) {
LongestCommonSubstring solver = new LongestCommonSubstring();
System.out.println(solver.findLength("TRANSFER", "TRANSFORM"));
System.out.println(solver.findLength("ABCDE", "ABFCE"));
}
}
5
2
How do you reconstruct the actual substring?
To extract the actual substring, track the ending index alongside the maximum length. When you find a new maximum, record the current position. The substring is the last maxLen characters ending at that position.
package com.bank.service;
public class LongestCommonSubstringWithReconstruction {
public String findSubstring(String a, String b) {
int m = a.length();
int n = b.length();
int[][] dp = new int[m + 1][n + 1];
int maxLen = 0;
int endIndexA = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endIndexA = i;
}
}
}
}
return a.substring(endIndexA - maxLen, endIndexA);
}
public static void main(String[] args) {
LongestCommonSubstringWithReconstruction solver =
new LongestCommonSubstringWithReconstruction();
System.out.println(solver.findSubstring("TRANSFER", "TRANSFORM"));
}
}
TRANS
How do you optimize space with a rolling row?
Since each cell only depends on the diagonal cell from the previous row, you can use a single 1D array and fill it from right to left to avoid overwriting the diagonal value before it is read. This reduces space from O(m * n) to O(n).
package com.bank.service;
public class LongestCommonSubstringOptimized {
public int findLength(String a, String b) {
int m = a.length();
int n = b.length();
int[] prev = new int[n + 1];
int maxLen = 0;
for (int i = 1; i <= m; i++) {
int[] curr = new int[n + 1];
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
curr[j] = prev[j - 1] + 1;
maxLen = Math.max(maxLen, curr[j]);
}
// else curr[j] stays 0
}
prev = curr;
}
return maxLen;
}
}
How is this different from Longest Common Subsequence?
This is the most common interview trap. Both use a 2D table with the same match rule (diagonal + 1), but they differ in the mismatch rule and where the answer is found.
| Aspect | Longest Common Substring | Longest Common Subsequence |
|---|---|---|
| Contiguity | Must be contiguous | Gaps allowed |
| Mismatch rule | dp[i][j] = 0 (reset) | dp[i][j] = max(top, left) |
| Answer location | Global max over all cells | Bottom-right corner dp[m][n] |
| Cell meaning | Run length ending here | Best length up to here |
package com.bank.core;
// Example: A = "ABCDE", B = "ABFCE"
// Longest Common Substring: "AB" (length 2) - must be contiguous
// LCS: "ABCE" (length 4) - gaps allowed between A,B,C,E
What about a banking use case?
At the National Bank of India, a forensics tool compares two server request logs to find the longest identical contiguous block that might indicate a replayed request batch. Because a replay must be a contiguous identical run, the substring DP is the right choice.
package com.bank.service;
public class ReplayDetector {
private final LongestCommonSubstringWithReconstruction solver =
new LongestCommonSubstringWithReconstruction();
public String findReplayedBlock(String log1, String log2) {
String block = solver.findSubstring(log1, log2);
if (block.length() >= 5) {
System.out.println("ALERT: Possible replay detected: " + block);
}
return block;
}
public static void main(String[] args) {
ReplayDetector detector = new ReplayDetector();
String log1 = "ABCWDTRANSFERWDX";
String log2 = "XYTRANSFERWDABC";
detector.findReplayedBlock(log1, log2);
}
}
ALERT: Possible replay detected: TRANSFERWD
What are common mistakes?
The most common mistake is confusing this with LCS and using max(top, left) on mismatch instead of resetting to zero. Another mistake is looking for the answer at dp[m][n] instead of tracking the global maximum. A third mistake is forgetting to explicitly set cells to zero on mismatch when the array is not pre-initialized.
package com.bank.core;
// WRONG: using LCS mismatch rule
if (a.charAt(i-1) == b.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // WRONG for substring!
}
// CORRECT: reset to zero on mismatch
if (a.charAt(i-1) == b.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 0; // contiguous run is broken
}
What should a senior engineer know?
A senior engineer should know that for very long strings, suffix arrays or suffix trees can solve this in O(m + n) time, though they are more complex to implement. The rolling-row DP is the practical middle ground for interviews. The substring problem also has applications in plagiarism detection, DNA sequence analysis, and log forensics.
package com.bank.core;
// Senior notes:
// 1. Suffix array/tree: O(m+n) for longest common substring
// 2. Rolling row: O(n) space, sufficient for interviews
// 3. Key trap: substring vs subsequence mismatch rule
// 4. Applications: plagiarism detection, DNA analysis, log replay detection
// 5. Track ending index alongside max length for reconstruction
Visual Overview
DP table for A = "ABCX" and B = "ZABC":
"" Z A B C
"" [ 0 0 0 0 0 ]
A [ 0 0 1 0 0 ]
B [ 0 0 0 2 0 ]
C [ 0 0 0 0 3 ] <- global max = 3
X [ 0 0 0 0 0 ] <- reset to 0
Match: diagonal + 1 (extend the run)
Mismatch: 0 (break the run)
Answer: max over ALL cells = 3
Substring: "ABC" (ending at A[2] and B[3])
Contrast with LCS table:
"" Z A B C
"" [ 0 0 0 0 0 ]
A [ 0 0 1 1 1 ]
B [ 0 0 1 2 2 ]
C [ 0 0 1 2 3 ]
X [ 0 0 1 2 3 ] <- answer at corner = 3
Note: LCS mismatch inherits from neighbors
Substring mismatch resets to 0
Key Takeaway
Longest Common Substring finds the longest contiguous block of characters that appears in both strings. You define dp[i][j] as the length of the common run ending exactly at positions A[i-1] and B[j-1]. When characters match you extend the diagonal by one, building a contiguous run. When they differ the run is broken and the cell resets to zero.
The two critical differences from the Longest Common Subsequence are the mismatch rule and the answer location. LCS inherits from neighbors on a mismatch and reads the answer from the bottom-right corner. Longest Common Substring resets to zero and finds the answer as the global maximum over all cells in the table. Conflating these two is a classic interview trap.
The time and space complexity are both O(m * n), and space reduces to O(n) with a rolling row that keeps only the previous row. To reconstruct the actual substring rather than just the length, track the ending index alongside the maximum length and extract the last maxLen characters from that position.
At the National Bank of India, a forensics tool compared two server request logs to find the longest identical contiguous block that might indicate a replayed request batch. Because a replay is a contiguous run, the substring DP with its reset-to-zero rule was the correct choice, and the rolling-row optimization kept memory manageable for long logs.
Remember one sentence: match extends the diagonal, mismatch resets to zero, and the answer is the global maximum cell, not the corner.
---