Longest Palindromic Substring Cont…

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 2: It’s not always about doing the right thing, sometimes not doing some things makes a great difference too. Enough of the lecture, let’s dive right into the solution.

So, while we still borrow the major part of the solution from our previous approach (which you can view here), we can make it a tad bit faster by skipping the last few iterations. In case we know for a fact that there is no chance of finding a longer palindrome anymore, it is simply redundant to invest runtime in checking these characters.

//Approach 2
//Runtime: 4ms
//Memory usage: 38.1MB
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-max/2; 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!