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

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

/*

time:O(n), space:O(1)

*/

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right &&                                                      !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right &&                                                      !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (Character.toLowerCase(s.charAt(left)) !=                             Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}