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.

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();
}