Definition
- DP table where
dp[i][j]holds the length of the common contiguous run ending exactly ata[i-1]andb[j-1]. - Match rule is
dp[i][j] = 1 + dp[i-1][j-1], extending the diagonal run by one. - Mismatch rule resets
dp[i][j] = 0because any gap breaks contiguity. - Answer is the maximum value found anywhere in the table, tracked during the fill.
- **O(m*n) time and space**, reducible to O(min(m,n)) with rolling rows.
The National Bank of India compares two transaction narration strings to find the longest identical unbroken phrase they share. A long shared phrase suggests both narrations came from the same automated upstream source. Rajesh aligns them in a grid and measures the longest diagonal run of matches.
Understanding the Concepts
What is the problem?
Given two strings, find the length of the longest substring that appears in both. A substring must be contiguous. For "SALARYPAY" and "MYSALARY", the longest common substring is "SALARY" with length 6.
package com.bank.dsa;
public class LongestCommonSubstring {
public static int longestCommonSubstring(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
int best = 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] = 1 + dp[i - 1][j - 1];
best = Math.max(best, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return best;
}
}
Why does this matter in banking?
During reconciliation at the National Bank of India, Rajesh compares transaction narration strings from two different systems. A long shared contiguous phrase strongly suggests both narrations were generated by the same automated upstream system, helping identify the source of discrepancies.
package com.bank.service;
import com.bank.dsa.LongestCommonSubstring;
public class NarrationMatcher {
public void compare(String narration1, String narration2) {
int len = LongestCommonSubstring.longestCommonSubstring(narration1, narration2);
System.out.println("Narration 1: " + narration1);
System.out.println("Narration 2: " + narration2);
System.out.println("Longest shared phrase length: " + len);
}
public static void main(String[] args) {
new NarrationMatcher().compare("SALARYPAY", "MYSALARY");
}
}
Narration 1: SALARYPAY
Narration 2: MYSALARY
Longest shared phrase length: 6
How does the recurrence work?
The table entry dp[i][j] represents the length of the longest common substring that ends exactly at position i of string A and position j of string B. When those two characters match, the run is one longer than the diagonal cell: dp[i][j] = 1 + dp[i-1][j-1]. When they differ, no common substring can end here, so it resets to 0.
package com.bank.dsa;
public class RecurrenceDemo {
public static void main(String[] args) {
String a = "AB", b = "XAB";
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
int best = 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] = 1 + dp[i - 1][j - 1];
best = Math.max(best, dp[i][j]);
}
System.out.println("dp[" + i + "][" + j + "]=" + dp[i][j]
+ " (a='" + a.charAt(i-1) + "' b='" + b.charAt(j-1) + "')");
}
}
System.out.println("Best: " + best);
}
}
dp[1][1]=0 (a='A' b='X')
dp[1][2]=1 (a='A' b='A')
dp[1][3]=0 (a='A' b='B')
dp[2][1]=0 (a='B' b='X')
dp[2][2]=0 (a='B' b='A')
dp[2][3]=2 (a='B' b='B')
Best: 2
Why is the answer the table maximum, not a corner?
Unlike the longest common subsequence where the answer is in dp[m][n], the longest common substring can end at any pair of positions. So the answer is the maximum value found anywhere in the table, which you track with a running variable during the fill.
package com.bank.dsa;
public class MaxAnywhereDemo {
public static void main(String[] args) {
// The longest common substring might end in the middle, not at the end
System.out.println(LongestCommonSubstring.longestCommonSubstring("XABCY", "ZABCW")); // 3 ("ABC")
// Answer is 3, found at dp[4][4], not at dp[5][5]
}
}
3
How is this different from the Longest Common Subsequence?
| Aspect | Common Substring | Common Subsequence |
|---|---|---|
| Contiguity | Required | Not required |
| On mismatch | Reset to 0 | Keep max(top, left) |
| Answer location | Maximum in table | Corner dp[m][n] |
| Use case | Exact shared phrase | Ordered similarity |
package com.bank.dsa;
public class SubstringVsSubsequence {
public static void main(String[] args) {
String a = "ABCXYZ", b = "XYZABC";
System.out.println("Common Substring: " + LongestCommonSubstring.longestCommonSubstring(a, b)); // 3
System.out.println("Common Subsequence: " + LongestCommonSubsequence.lcs(a, b)); // 3
}
}
What are the edge cases?
If either string is empty, the result is 0. If both strings are identical, the result is their length. If they share no common character, the result is 0.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(LongestCommonSubstring.longestCommonSubstring("", "ABC")); // 0
System.out.println(LongestCommonSubstring.longestCommonSubstring("ABC", "ABC")); // 3
System.out.println(LongestCommonSubstring.longestCommonSubstring("ABC", "XYZ")); // 0
}
}
0
3
0
What is the time and space complexity?
Time is O(m*n) where m and n are the lengths of the two strings. Space is O(m*n) for the table, reducible to O(min(m,n)) by using only two rolling rows since each row depends only on the previous row.
What are common interview follow-up questions?
- How would you return the actual substring, not just the length?
- How would you find all common substrings of a given minimum length?
- Can this be solved with a suffix array in O((m+n) log(m+n)) time?
- How does this relate to the edit distance problem?
Visual Overview
Strings: A = "SALARY" B = "MYSALARY"
DP Table (showing non-zero values):
M Y S A L A R Y
S 0 0 1 0 0 0 0 0
A 0 0 0 2 0 1 0 0
L 0 0 0 0 3 0 0 0
A 0 0 0 1 0 4 0 0
R 0 0 0 0 0 0 5 0
Y 0 1 0 0 0 0 0 6 ← max!
Answer: 6 ("SALARY")
┌─────────────────────────────┐
│ Match: extend diagonal +1 │
│ Mismatch: reset to 0 │
│ Answer: max in entire table│
└─────────────────────────────┘
Key Takeaway
The Longest Common Substring finds the longest contiguous run shared by two strings, and the mental model is a grid where each cell holds the length of the common run ending at that pair of positions. On a character match, the run extends from the diagonal by one. On a mismatch, contiguity breaks and the cell resets to zero. The answer is the maximum value anywhere in the table.
Rajesh at the National Bank of India uses this during reconciliation to compare transaction narrations from different systems. A long shared contiguous phrase is a strong signal that both narrations came from the same automated source. The algorithm fills the grid in O(m*n) time and space, with space reducible to O(min(m,n)) using two rolling rows.
The crucial difference from the longest common subsequence is the reset on mismatch. The subsequence version carries the better neighbor forward (gaps allowed), so its answer sits in the corner of the table. The substring version resets to zero (contiguity required), so its answer can be anywhere in the table.
Understanding this reset-versus-carry distinction is what shows an interviewer you know both patterns and can pick the right one for the problem at hand.
Remember one sentence: on a match extend the diagonal run by one, on a mismatch reset to zero, and the answer is the maximum value found anywhere in the table.
---