Longest Palindromic Substring

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

You may view the full question here.

Approach 1: Let’s start with a naive approach. As the example suggests, there are two patterns in which the palindromes can occur — with odd number of characters and even number of characters. And therefore the there can one or two characters occurring exactly in the middle of the palindromic string. We iterate through each character in a given string to see if there can be a possible palindrome (of odd or even length) formed with this character as the mid or one of the mid characters.

//Approach 1:
//Runtime: 6ms
//Memory usage: 38MB
class Solution {
    public String longestPalindrome(String s) {
        int max = 0;
        char[] chars = s.toCharArray();
        int count = 0;
        String sub = "";
        int start, end;
        for(int i = 0; i<chars.length; i++){
            count = oddCheck(chars, i);
            if(count>max){
                max = count;
                start = i-(count-1)/2;
                end = i+(count-1)/2;
                sub = s.substring(start,end+1);
            }
            count = evenCheck(chars, i);
            if(count>max){
                max = count;
                start = i-count/2 +1;
                end = i+count/2;
                sub = s.substring(start,end+1);
            }
        }
        return sub;
    }
    
    private int oddCheck(char[] chars, int mid){
        int count = 1;
        for(int left = mid - 1, right = mid + 1; left>=0 && right<chars.length; left--, right++){
            if(chars[left]!=chars[right]){
                return count;
            }
            count+=2;
        }
        return count;
    }
    
    private int evenCheck(char[] chars, int left){
        int count = 0;
        for(int right = left + 1; left>=0 && right<chars.length; left--, right++){
            if(chars[left]!=chars[right]){
                return count;
            }
            count+=2;
        }
        return count;
    }
}

Find more posts here.

Cheers & Chao!