The Longest Common Substring problem asks us to find the longest contiguous sequence of characters that appears in two strings.
The word contiguous is essential.
Consider:
ABABC
BABCA
The string:
BABC
appears continuously in both inputs.
Therefore:
Longest Common Substring = "BABC"
Length = 4
What is a substring?
A substring contains consecutive characters from the original string.
For:
ABCDE
valid substrings include:
ABC
BCD
DE
C
But:
ACE
is not a substring because its characters are not contiguous.
Another example
Consider:
programming
gaming
A common contiguous section is:
ming
so the longest common substring has length 4.
Brute-force approach
A straightforward solution is to generate every substring of the first string and check whether it appears in the second.
A string of length n has approximately:
n × (n + 1) / 2
substrings.
Testing all of them quickly becomes expensive, so a dynamic-programming approach is usually preferred for standard algorithmic problems.
Dynamic Programming definition
For strings a and b, define:
dp[i][j]
as the length of the longest common substring that ends exactly at a[i - 1] and b[j - 1].
If the two current characters match:
a[i - 1] === b[j - 1]
then:
dp[i][j] = dp[i - 1][j - 1] + 1
If they do not match:
dp[i][j] = 0
The reset to zero is what enforces contiguity.
Example DP table
For:
a = ABABC
b = BABCA
we obtain conceptually:
B A B C A
A 0 1 0 0 1
B 1 0 2 0 0
A 0 2 0 0 1
B 1 0 3 0 0
C 0 0 0 4 0
The largest value is:
4
which corresponds to:
BABC
Why the answer is not necessarily the final cell
The best common substring can end anywhere in the two strings.
For this reason, we maintain a variable such as:
maxLength
while filling the matrix.
TypeScript implementation
function longestCommonSubstringLength(
a: string,
b: string
): number {
const dp: number[][] = Array.from(
{ length: a.length + 1 },
() => new Array(b.length + 1).fill(0)
);
let maxLength = 0;
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}
For:
longestCommonSubstringLength("ABABC", "BABCA");
we get:
4
Returning the actual substring
To return the substring itself, keep track of where the best match ends.
function longestCommonSubstring(
a: string,
b: string
): string {
const dp: number[][] = Array.from(
{ length: a.length + 1 },
() => new Array(b.length + 1).fill(0)
);
let maxLength = 0;
let endIndex = 0;
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i;
}
}
}
}
return a.slice(endIndex - maxLength, endIndex);
}
Complexity
For string lengths n and m:
Time Complexity: O(n × m)
Space Complexity: O(n × m)
Every pair of positions is examined once.
Space optimization
The current row depends only on the previous row.
Therefore, the full matrix is unnecessary when only the length is required.
Memory can be reduced to:
O(min(n, m))
Example:
function longestCommonSubstringOptimized(
a: string,
b: string
): number {
if (b.length > a.length) {
[a, b] = [b, a];
}
let previous = new Array(b.length + 1).fill(0);
let maxLength = 0;
for (let i = 1; i <= a.length; i++) {
const current = new Array(b.length + 1).fill(0);
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
current[j] = previous[j - 1] + 1;
maxLength = Math.max(maxLength, current[j]);
}
}
previous = current;
}
return maxLength;
}
Longest Common Substring vs. Longest Common Subsequence
These problems are frequently confused.
Suppose:
a = ABCDEF
b = ACEF
The Longest Common Subsequence can be:
ACEF
because its characters only need to remain in order.
They do not need to be adjacent.
A common substring, however, must be contiguous. In this example:
EF
is a valid common substring.
Difference in the DP recurrence
For Longest Common Substring, mismatch means:
dp[i][j] = 0
For Longest Common Subsequence, mismatch normally leads to:
dp[i][j] = max(
dp[i - 1][j],
dp[i][j - 1]
)
That single difference reflects the requirement that a substring remain continuous.
Text similarity
A long exact contiguous match can be a useful signal when comparing strings or documents.
For example:
customer_relationship_management
relationship_manager
contains a substantial common region.
Longest Common Substring alone is not a complete similarity metric, but it can be one feature in a larger matching system.
CRM and data deduplication
Suppose imported CRM data contains:
Arian Soleimanzadeh Software Engineer
Arian Soleimanzadeh
A large common substring may provide evidence that the records are related.
Production systems should combine this with other signals such as:
- Levenshtein Distance
- Email matching
- Phone matching
- Token similarity
- Data normalization
Bioinformatics
DNA and protein sequences can be treated as strings.
For example:
ACGTACGT
TTGTACGG
contains a long shared contiguous region.
Longest Common Substring concepts can help identify similar local sequence regions, although practical bioinformatics systems often use specialized sequence-alignment algorithms.
Version and sequence comparison
Consider two API paths:
/api/v1/customer/profile
/api/v2/customer/profile
A large common region is:
/customer/profile
Common-substring logic can therefore be useful as a building block in sequence comparison tools.
Plagiarism and document similarity
Long identical segments between documents can provide a signal for copied or repeated content.
Real plagiarism-detection systems generally combine this idea with tokenization, N-grams, fingerprinting, and semantic techniques.
Log and security analysis
Consider:
ERROR_AUTH_TOKEN_EXPIRED_USER_101
ERROR_AUTH_TOKEN_EXPIRED_USER_205
A long common segment can help identify that the entries belong to the same underlying error pattern.
Multiple optimal answers
There may be several longest common substrings with the same length.
For example:
a = abcXYZ123
b = abcABC123
both:
abc
123
have length 3.
If every answer is needed, store the end positions of all cells whose value equals the maximum.
Edge cases
Important cases include:
- One empty string
- No common characters
- Identical strings
- Multiple equally long matches
- Case-sensitive versus case-insensitive comparison
For case-insensitive matching, normalize the input before running the algorithm.
Common interview question
A typical problem asks:
Given two strings, find the length or value of their longest common substring.
A good explanation should cover:
- The substring must be contiguous.
dp[i][j]represents a match ending at the current positions.- A mismatch resets the current match to zero.
- A global maximum must be maintained.
- Time complexity is
O(n × m). - Memory can be optimized if necessary.
Common mistake: using the LCS recurrence
Writing:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
on mismatch solves the Longest Common Subsequence problem, not Longest Common Substring.
For substring matching, the correct mismatch behavior is:
dp[i][j] = 0
Are faster algorithms possible?
Yes.
For very large input sizes, advanced structures such as:
- Suffix Trees
- Suffix Arrays
- Suffix Automata
can provide more efficient solutions.
However, Dynamic Programming remains one of the clearest approaches for learning, interviews, and moderate input sizes.
Conclusion
The Longest Common Substring problem finds the longest contiguous sequence shared by two strings.
Its core recurrence is:
if a[i - 1] === b[j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1
else
dp[i][j] = 0
The standard solution uses:
Time: O(n × m)
Space: O(n × m)
with memory optimization down to:
O(min(n, m))
The key idea to remember is simple:
A substring must remain continuous, so any mismatch breaks the current matching chain.