Substring index out of bounds

Question

I am writing a simple program to find the longest palindrome in a string. What I'm doing is checking if each substring is a palindrome and then checking its length. If the length is greater than the previous length, then I have the new longest substring. For example, "babad", would return "bab" or "aba", either is fine. But my issue is that I get index out of bounds on my substring call and I can't figure out why.

public class LongestPal{
    public static void main(String[] args)
    {
        String test = new String("babad");
        String result = longestPalindrome(test);

    }
    public static String longestPalindrome(String s) {
        int length = 0;
        String answer = new String();

        for(int i = 0;i<=s.length();i++)
        {
            for(int j = 0; j<= s.length();j++)
            {
                String subStr = s.substring(i,j); // Get all substrings
                System.out.println(subStr); // Checking to see if all are printed

                boolean result = isPalindrome(subStr); //Check for palindrome
                if(result)
                {
                    if(length < subStr.length()) //If length of new substr is greater than the old one, 
                                                //the new answer will be longer substring
                    {
                        answer = subStr;   
                    }
                }
            }
        }
        return answer;
    }
    public static boolean isPalindrome(String s) //Recursive palindrome checker
    {
        if(s.length() == 0 || s.length() == 1)
            return true; 
        if(s.charAt(0) == s.charAt(s.length()-1))
            return isPalindrome(s.substring(1, s.length()-1));
        return false;
    }
}

When I print out, I get all the substring combinations, until "babbad" after that is when the error occurs.

Answer 1

Part A of the problem - Compiler error

1. Change your outer loop from for(int i = 0;i<=s.length();i++) to for(int i = 0;i<s.length();i++) as others have pointed out.
2. Change your inner loop from for(int j = 0; j<= s.length();j++) to for(int j = i; j< s.length();j++).

Your program is giving you out of bound exception because in the second iteration of your outer loop, your i becomes 1 and j starts from 0. And then you call the String's substring method as s.substring(1,0); which obviously gives you this exception.

Make the corrections as suggested and go from there on. Let us know if you need more help.

Part B of the problem - Faster algorithm

Here's a more efficient algorithm. I believe this should be the fastest one too.

    public static void main(String[] args) {        
    String s = "babad";

    int starter = 0;

    if(s.length() % 2 == 0) 
        starter = 1;

    String answer = "";
    Boolean found = Boolean.FALSE;
    while(starter < s.length() - 1) {
        for(int i=0; i<=starter; i++) {
            if(isPelindrom(answer = s.substring(i, i+ s.length() - starter))) {
                found = Boolean.TRUE;
                break;
            }
        }
        if(found) break;
        starter = starter + 1;          
    }
    if(!found) answer = String.valueOf(s.charAt(0));
    System.out.println("The answer is " + answer);

}

public static Boolean isPelindrom(String s) {
    return s.equalsIgnoreCase(new StringBuilder(s).reverse().toString());
}

Let me know if you need additional help.

Answer 2

So the error in my code turned out to be when i>j as pointed out by some of the people in the comments. Thus, simply making j=i when searching for palindromes resolved the issue.

You'll also notice that you don't ever see length change and this is another error in the code. Once the answer is updated, the length must be changed to the length of the answer. A simple fix for this is making length = subStr.length() in the second "if" statement.

The algorithm still not fast as it will run with complexity of O(n^3).

Answer 3

shouldn't you be iterating from 0 to s.length-1 ? which would mean your loop condition to be:

for(int i = 0;i<s.length();i++)

and a similar one for the next loop with j

Not doing that could result in index out of bounds for sure.

Answer 4

You need to change your loop condition. It should be only < not <=. Because If you check the length of 'babad' it will give you 5 but index start from 0 and end on 4 for this. So you need to change the loop condition and it will solve the problem.