"A creative life cannot be sustained by approval any more than it can be destroyed by criticism."
Hey coder. We begin with a new question in this article, "Longest Common Substring".
Before moving forward, we want you to go through the problem outline.
In this problem, you are given two strings s1 and s2 and you are required to print the length of the longest common substring of the two strings.
To understand the problem, we say that s1= "pqabcxy" and s2= "xyzabcp". Here, the longest common substring is "abc" of length 3.
You already know that a string of length n has a total of n(n+1)/2 substrings.
BRUTE APPROACH
The simplest way of solving the problem is by adding all the substrings of s1 in one arraylist and adding all the substrings of s2 in another arraylist.
Then we run a nested loop with the substrings of s1 as the outer loop and the substrings of s2 as the inner loop.
We compare the substrings of the inner loop with that of the outer loop.
As we find any common substrings, we store them in a third arraylist and further print the length of the largest common substring.
However,the time complexity of this approach is O(n5).
This is because the outer loop runs for n2 elements and similarly the inner loop also runs for n2 elements. Around n time is used for comparing the 2 substrings.
Therefore, the total time complexity of the approach is O(n2 * n2 * n)= O(n5).
Hence, this approach is not desirable.
OPTIMIZED APPROACH
In this method, we compare all the prefixes of s1 with all the prefixes of s2 and find their longest common suffix. The length of this longest common suffix will be our desired answer.
Let's understand the above statement in detail.
The above figure shows all the prefixes of s1 and s2.
We see that for a string of length n, the number of prefixes are n. Hence the complexity of the nested loop in this case if O(n*n)=O(n2).
Now, to find the suffix of the compared prefixes we make a table as shown in figure 2 where the prefixes of s1 are along the y-axis and the prefixes of s2 are along the x-axis.
Hence, each cell of the following table is the suffix of its corresponding prefixes in x and y axes.
In figure 2, the suffixes highlighted with blue were found. The rest of the cells store null. Out of all the suffixes, we find that "abc" has the longest length, hence it is our desired answer.
Reader, we have found the best approach, now we need to discuss "WHY" it gives us the correct answer.
WHY
We now understand the reason behind using the above approach.
For string "pqabcxy", the substring "abc" must be a suffix of some prefix of s1. It is not a suffix of "p" or "pq" or "pqa" or "pqab". But it is a suffix of "pqabc".
Similarly, for string "xyzabcp", the substring "abc" must be a suffix of some prefix of s2. It is not a suffix of "x" or "xy" or "xyz" or "xyza" or "xyzab".
But it is a suffix of "xyzabc".
We now compare "pqabc" and "xyzabc" and find that the longest common substring is "abc" which is our desired answer.
HOW
Let us consider r1 and c1 as "rest of the prefix 1" and "last character of prefix 1" respectively.
Similarly consider r2 and c2 as "rest of the prefix 2" and "last character of prefix 2" respectively.
For example, if prefix 1 is "pqabc", then r1= "pqab" and c1= 'c'.
Now, if c1 and c2 are not the same, then no common suffix is possible and hence, the length is 0.
Else, if c1 and c2 are the same then, the length of the common suffix of prefix 1 and prefix 2 is equal to one more than the common suffix of strings r1 and r2.
To see a dry run of this explanation, you can watch the solution video .
We now want you to write the code for this problem based on our discussion.
If you get stuck anywhere, you can simply refer to the code given below which is quite straight forward.
import java.io.*;
import java.util.*;
public class Main {
public static int solution(String s1, String s2){
int[][]dp=new int[s1.length()+1][s2.length()+1];
int max=0;
for(int i=1;i < dp.length;i++){
for(int j=1;j< dp[0].length;j++){
char c1=s1.charAt(i-1);
char c2=s2.charAt(j-1);
if(c1!=c2){
dp[i][j]=0;
}else{
dp[i][j]=dp[i-1][j-1]+1;
}
if(dp[i][j]>max){
max=dp[i][j];
}
}
}
return max;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String s1 = scn.next();
String s2 = scn.next();
System.out.println(solution(s1,s2));
}
}
java;
true";
TIME COMPLEXITY- O(n2)
SPACE COMPLEXITY- O(n2)
We end the problem's discussion here. We hope you were able to understand it.
In case you still have any doubts, we strongly recommend you to watch the solution video of the question.
