Given two strings str1 and str2, find the length of their longest common substring.
A substring is a contiguous sequence of characters within a string.
Input: str1 = "abcde", str2 = "abfce"
Output: 2
Explanation: The longest common substring is "ab", which has a length of 2.
Input: str1 = "abcdxyz", str2 = "xyzabcd"
Output: 4
Explanation: The longest common substring is "abcd", which has a length of 4.
Input: str1 = "abcdef", str2 = "ghijkl"
We are given a string S, the simplest approach will be to generate all the subsequences and store them, then manually find out the longest common substring. This naive approach will give us the correct answer but to generate all the subsequences, we will require exponential ( 2n ) time. Therefore we will try some other approaches.
We can modify the approach we used in the article Longest Common Subsequence, in order to find the longest common substring. The main distinguishing factor between the two is the consecutiveness of the characters.
While finding the longest common subsequence, we were using two pointers (ind1 and ind2) to map the characters of the two strings. We will again have the same set of conditions for finding the longest common substring, with slight modifications to what we do when the condition becomes true.
We will try to form a solution in the bottom-up (tabulation) approach. We will set two nested loops with loop variables i and j.
Thinking in terms of consecutiveness of characters, we have two conditions:#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the length of
the Longest Common Substring (LCS) */
int longestCommonSubstr(string str1, string str2) {
int n = str1.size();
int m = str2.size();
// Initialize a 2D DP table with dimensions
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// Initialize the answer variable
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// Characters match, increment substring length
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
/* Update the maximum substring
length found so far */
ans = max(ans, dp[i][j]);
} else {
/* Characters don't match,
substring length becomes 0 */
dp[i][j] = 0;
}
}
}
// Return the length of Longest Common Substring
return ans;
}
};
int main() {
string s1 = "abcjklp";
string s2 = "acjkp";
// Create an instance of Solution class
Solution sol;
// Print the result
cout << "The Length of Longest Common Substring is " << sol.longestCommonSubstr(s1, s2) << endl;
return 0;
}
import java.util.*;
class Solution {
/* Function to find the length of
the Longest Common Substring (LCS) */
public int longestCommonSubstr(String str1, String str2) {
int n = str1.length();
int m = str2.length();
// Initialize a 2D DP table with dimensions
int[][] dp = new int[n + 1][m + 1];
// Initialize the answer variable
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// Characters match, increment substring length
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
/* Update the maximum substring
length found so far */
ans = Math.max(ans, dp[i][j]);
} else {
/* Characters don't match,
substring length becomes 0 */
dp[i][j] = 0;
}
}
}
// Return the length of Longest Common Substring
return ans;
}
public static void main(String[] args) {
String s1 = "abcjklp";
String s2 = "acjkp";
// Create an instance of Solution class
Solution sol = new Solution();
// Print the result
System.out.println("The Length of Longest Common Substring is " + sol.longestCommonSubstr(s1, s2));
}
}
class Solution:
""" Function to find the length of
the Longest Common Substring (LCS) """
def longestCommonSubstr(self, str1, str2):
n = len(str1)
m = len(str2)
# Initialize a 2D DP table with dimensions
dp = [[0] * (m + 1) for _ in range(n + 1)]
# Initialize the answer variable
ans = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
# Characters match, increment substring length
if str1[i - 1] == str2[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
""" Update the maximum substring
length found so far """
ans = max(ans, dp[i][j])
else:
""" Characters don't match,
substring length becomes 0 """
dp[i][j] = 0
# Return the length of Longest Common Substring
return ans
if __name__ == "__main__":
s1 = "abcjklp"
s2 = "acjkp"
# Create an instance of Solution class
sol = Solution()
# Print the result
print("The Length of Longest Common Substring is", sol.longestCommonSubstr(s1, s2))
class Solution {
/* Function to find the length of
the Longest Common Substring (LCS) */
longestCommonSubstr(str1, str2) {
const n = str1.length;
const m = str2.length;
// Initialize a 2D DP table with dimensions
const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
// Initialize the answer variable
let ans = 0;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
// Characters match, increment substring length
if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
/* Update the maximum substring
length found so far */
ans = Math.max(ans, dp[i][j]);
} else {
/* Characters don't match,
substring length becomes 0 */
dp[i][j] = 0;
}
}
}
// Return the length of Longest Common Substring
return ans;
}
}
const s1 = "abcjklp";
const s2 = "acjkp";
// Create an instance of Solution class
const sol = new Solution();
// Print the result
console.log("The Length of Longest Common Substring is " + sol.longestCommonSubstr(s1, s2));
If we observe the relation obtained in tabultaion approach, dp[i-1][j-1]. We are using just the previous row, dp[ind1-1][ ], in order to calculate the present row.
So we are not required to contain an entire array, we can simply have two rows 'prev' and 'cur' where prev corresponds to dp[ind-1] and cur to dp[ind].
After declaring 'prev' and 'cur', replace dp[ind-1] to prev and dp[ind] with cur in the tabulation code. Following the same logic of tabulation, we will calculate cur[ind] and store the maximum of all the in 'ans variable in each iteration and after the inner loop executes, we will set prev = cur, so that the cur row can serve as prev for the next index.
After end of the execution, return 'ans' as our answer, as it will hold the maximum length of common substring.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the length of
the Longest Common Substring (LCS) */
int longestCommonSubstr(string str1, string str2) {
int n = str1.size();
int m = str2.size();
/* Initialize two vectors to store
previous and current row values*/
vector<int> prev(m+1, 0);
vector<int> cur(m+1, 0);
/* Initialize the answer variable to
store the maximum LCS length found*/
int ans = 0;
// Loop through both strings
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
// Characters match, increment substring length
if(str1[i-1] == str2[j-1]){
int val = 1 + prev[j-1];
cur[j] = val;
/* Update the maximum substring
length found so far*/
ans = max(ans, val);
}
else{
/* Characters don't match,
substring length becomes 0*/
cur[j] = 0;
}
}
/* Update the previous row with
the values of the current row*/
prev = cur;
}
// Return the length of Longest Common Substring
return ans;
}
};
int main() {
string s1 = "abcjklp";
string s2 = "acjkp";
// Create an instance of Solution class
Solution sol;
// Print the result
cout << "The Length of Longest Common Substring is " << sol.longestCommonSubstr(s1, s2) << endl;
return 0;
}
import java.util.*;
class Solution {
/* Function to find the length of
the Longest Common Substring (LCS) */
public int longestCommonSubstr(String str1, String str2) {
int n = str1.length();
int m = str2.length();
/* Initialize two arrays to store
previous and current row values*/
int[] prev = new int[m + 1];
int[] cur = new int[m + 1];
/* Initialize the answer variable to
store the maximum LCS length found*/
int ans = 0;
// Loop through both strings
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// Characters match, increment substring length
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
int val = 1 + prev[j - 1];
cur[j] = val;
/* Update the maximum substring
length found so far*/
ans = Math.max(ans, val);
} else {
/* Characters don't match,
substring length becomes 0*/
cur[j] = 0;
}
}
/* Update the previous row with
the values of the current row*/
System.arraycopy(cur, 0, prev, 0, m + 1);
}
// Return the length of Longest Common Substring
return ans;
}
public static void main(String[] args) {
String s1 = "abcjklp";
String s2 = "acjkp";
// Create an instance of Solution class
Solution sol = new Solution();
// Print the result
System.out.println("The Length of Longest Common Substring is " + sol.longestCommonSubstr(s1, s2));
}
}
class Solution:
""" Function to find the length of
the Longest Common Substring (LCS) """
def longestCommonSubstr(self, str1, str2):
n = len(str1)
m = len(str2)
""" Initialize two lists to store
previous and current row values """
prev = [0] * (m + 1)
cur = [0] * (m + 1)
""" Initialize the answer variable to
store the maximum LCS length found """
ans = 0
# Loop through both strings
for i in range(1, n + 1):
for j in range(1, m + 1):
# Characters match, increment substring length
if str1[i - 1] == str2[j - 1]:
val = 1 + prev[j - 1]
cur[j] = val
""" Update the maximum substring
length found so far """
ans = max(ans, val)
else:
""" Characters don't match,
substring length becomes 0 """
cur[j] = 0
""" Update the previous row with
the values of the current row"""
prev[:] = cur[:]
# Return the length of Longest Common Substring
return ans
if __name__ == "__main__":
s1 = "abcjklp"
s2 = "acjkp"
# Create an instance of Solution class
sol = Solution()
# Print the result
print("The Length of Longest Common Substring is", sol.longestCommonSubstr(s1, s2))
class Solution {
/* Function to find the length of
the Longest Common Substring (LCS) */
longestCommonSubstr(str1, str2) {
const n = str1.length;
const m = str2.length;
/* Initialize two arrays to store
previous and current row values */
const prev = new Array(m + 1).fill(0);
const cur = new Array(m + 1).fill(0);
/* Initialize the answer variable to
store the maximum LCS length found */
let ans = 0;
// Loop through both strings
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
// Characters match, increment substring length
if (str1[i - 1] === str2[j - 1]) {
const val = 1 + prev[j - 1];
cur[j] = val;
/* Update the maximum substring
length found so far */
ans = Math.max(ans, val);
} else {
/* Characters don't match,
substring length becomes 0 */
cur[j] = 0;
}
}
/* Update the previous row with
the values of the current row */
for (let k = 0; k <= m; k++) {
prev[k] = cur[k];
}
}
// Return the length of Longest Common Substring
return ans;
}
}
const s1 = "abcjklp";
const s2 = "acjkp";
// Create an instance of Solution class
const sol = new Solution();
// Print the result
console.log("The Length of Longest Common Substring is " + sol.longestCommonSubstr(s1, s2));
Q: How is this different from Longest Common Subsequence (LCS)?
A: LCS allows characters to be non-contiguous, whereas Longest Common Substring (LCS) requires contiguous matches. Example: str1 = "abcde", str2 = "ace" → LCS = "ace" (length 3). str1 = "abcde", str2 = "cde" → LCS (Substring) = "cde" (length 3).
Q: Why do we need to track the maximum value separately?
A: The longest substring can end anywhere in str1 or str2. Thus, we must store the maximum encountered.
Q: How would you reconstruct the actual longest common substring instead of just its length?
A: Store end_index, then extract the substring using str1[end_index - max_length : end_index].
Q: Can this problem be solved using a suffix tree?
A: Yes! Suffix trees can efficiently find the longest common substring in O(n + m) time.