Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

/*
There are two conditions, like "acbbc" and "acbcb". The first one's longest palindromic substring is even number and the second one is odd number. We need discuss these two conditions each time to see which one is longer.

time:O(n^2), space:O(1)
*/

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        } 
        String ans = "";
        int maxCount = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            int oddLength = computePalindromeLength(s, i, i);
            int evenLength = computePalindromeLength(s, i, i + 1);
            if (oddLength > evenLength && 2 * oddLength - 1 > maxCount) {
                ans = s.substring(i - oddLength + 1, i + oddLength);
                maxCount = 2 * oddLength - 1;
            } else if (oddLength <= evenLength && 2 * evenLength > maxCount) {
                ans = s.substring(i - evenLength + 1, i + evenLength + 1);
                maxCount = 2 * evenLength;
            }
        }
        return ans;
    }
    public int computePalindromeLength(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left--) != s.charAt(right++)) {
                break;
            }
            count++;
        }
        return count;
    }
}