Debugging code to find longest palindrome in a string

Question

I'm trying to understand a code fragment that finds the longest palindrome in a given string. Here's the code segment

public static String longestPalindromeString(String in) {
        char[] input = in.toCharArray();
        int longestPalindromeStart = 0;
        int longestPalindromeEnd = 0;

        for (int mid = 0; mid < input.length; mid++) {
            // for odd palindrom case like 12321, 3 will be the mid
            int left = mid-1;
            int right = mid+1;
            // we need to move in the left and right side by 1 place till they reach the end
            while (left >= 0 && right < input.length) {
                // below check to find out if its a palindrome
                if (input[left] == input[right]) {
                    // update global indexes only if this is the longest one till now
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                left--;
                right++;
            }
            // for even palindrome, we need to have similar logic with mid size 2
            // for that we will start right from one extra place
            left = mid-1;
            right = mid + 2;// for example 12333321 when we choose 33 as mid
            while (left >= 0 && right < input.length)
            {
                if (input[left] == input[right]) {
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                left--;
                right++;
            }
        }
        // we have the start and end indexes for longest palindrome now
        return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
    }

}

However, the code segment seems to be failing for the inputs "bb" returns "b" and "abb" returns "a" instead of bb.

Any thoughts on whats causing the bug?

Source for the code segment .

Answer 1

To fix this change the following:

1. In the while, add a break to break from the while once two characters are not equal.

   while(/*....*/)
   {
        if(/*...*/)
        {
            //....
        }
        else           // add this
            break;     // and this   
   }
   

2. The initial setting of left and right for the even case is wrong. It assumes that the mid two characters are the same. Change it to

   left = mid;
   right = mid+1;
   

This is exactly as what is stated in the comments of the original code... -_- which I just read.