Longest Substring in Java

Question

This is my function for determining the Longest Substring between two strings in Java.

public class Main {
 public static String longestSubstring(String str1, String str2){
 int row = str1.length();
 int col = str2.length();
 int[][] checker = new int[row][col];
 int max = 0;
 int r = 0;
 int c = 0;
 for(int i=0; i < row; i++){
 for(int j=0; j < col; j++){
 if(str1.charAt(i) == str2.charAt(j)){
 if((i -1 > 0) && (j -1 >0)){
 checker[i][j] = checker[i-1][j-1] +1;
 }else{
 checker[i][j]++;
 }
 max = checker[i][j];
 r = i;
 c = j;
 }else continue;
 }
 }
 StringBuilder sb = new StringBuilder();
 while(true){
 if(checker[r][c] == 0) break;
 sb.append(str1.charAt(r));
 r--;
 c--;
 }
 return sb.reverse().toString();
 }
 public static void main(String[] args) {
 // write your code here
 String str1 = "adedfrgyu";
 String str2 = "arvbfrgykset";
 String str3 = "aaaaaaatyuieo";
 String str4 = "aaaaaklui";
 System.out.println(longestSubstring(str1, str2));
 }
}

The code compiles, but wondering is the algorithm is correct. It passes all the test cases that I could make up.

• Eyal: Suggestion: use a random word generator for the test cases.
• Alexis Wilke: If you want to make sure that all cases are covered by your tests (good testing requires such) then you need a tool that generate coverage data. You run your tests, then check coverage. If a case is never hit (i.e. an if() or else block never entered) then you've got a problem in your tests.
• 200_success: Surely you could have come up with more test cases and discovered that your code doesn't work.
• greybeard: (I think I'd like Longest Common Substring much better as a title, with in Java optional if the first tag is java.)

Answer 1

I liked your DP approach and use of stringbuider instead of string.

1. But, the code gives null pointer exception :

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
   at Test.longestSubstring(Test.java:157)
   at Test.main(Test.java:22)
   

for the input System.out.println(longestSubstring("aabb", "akk"));

The reason is that whenever the resultant substring starts from index 0, this code will throw a null pointer exception because checker[0][0] is 1(instead of 0), if the first characters match. Because, you're using if(checker[r][c] == 0) break; as the criteria to end the while loop. One solution is to have the while loop run for max number of times. Other approach is to use an array of 1 greater size i.e. int[][] checker = new int[row+1][col+1];

2. Moreover, there is a small bug in this code :-

For input System.out.println(longestSubstring("aabb", "abbbb"));, the output is "bb". But, the right answer is "abb". Even for the given test cases,

 String str3 = "aaaaaaatyuieo";
 String str4 = "aaaaaklui";
 System.out.println(longestSubstring(str1, str2));

The answer should be "aaaaa". But, it returns "ui". The reason for that is that you should check if checker[i][j] is greater than max before assigning

max = checker[i][j];
r = i;
c = j;

3. You need not write else continue; as the last statement in the loop.

Here is the complete code:-

 public static String longestSubstring(String str1, String str2){
 int row = str1.length();
 int col = str2.length();
 int[][] checker = new int[row+1][col+1];
 int max = 0;
 int r = 0;
 int c = 0;
 for(int i = 1; i <= row; i++){
 for(int j = 1; j <= col; j++){
 if(str1.charAt(i-1) == str2.charAt(j-1)){
 checker[i][j] = checker[i-1][j-1] +1;
 if(checker[i][j] > max){
 max = checker[i][j];
 r = i;
 c = j;
 }
 }
 }
 }
 StringBuilder sb = new StringBuilder();
 while(true){
 if(checker[r][c] == 0) break;
 sb.append(str1.charAt(r-1));
 r--;
 c--;
 }
 return sb.reverse().toString();
}

• CiaPan: Please check your comment in 2. IMHO for input of "aabb" and "abbbb" the answer should be "abb", not "aab".