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, and there exists one unique longest palindromic substring.

Analysis

• 用start, end记录最长palindrome的位置
• i从0开始，每次找在i附近展开的最大palindrome长度，如果比之前长就更新start和end的位置
• 用helper function 来 return i附近palindrom的长度
• 用len1和len2保证奇数和偶数长度palindrome都能考虑到

Code

public class Solution {
    public String longestPalindrome(String s) {
        if (s==null || s.length()<=1) return s;
        //start and end record the longest substring start end positions
        int start = 0, end = 0;

        //for each i, expand around i to find the longest palindrome substring around i
        for(int i=0; i<s.length();i++){
            int oddlen = palindrome(s, i, i); //odd length palindrome
            int evenlen = palindrome(s, i, i+1); //even length palindrome
            int len = Math.max(oddlen, evenlen);
            if (len > end-start+1){ //update substring length if larger
                start = i-(len-1)/2;
                end = i+len/2;
            }
        }
        return s.substring(start, end+1);
    }

    //return longest palindrome length expand around position L and R
    private int palindrome(String s, int L, int R){
        while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)){
            L--;
            R++;
        }
        return R-L-1;
    }
}

Time/space complexity

• Time: O(n^2)
• Space: O(1)

Reference

Clean code book