5. Longest Palindromic Substring

Given a strings, find the longest palindromic substring ins. You may assume that the maximum length ofsis 1000.

Example:

Input:
 "babad"

Output:
 "bab"

Note:
 "aba" is also a valid answer.

Example:

Input:
 "cbbd"

Output:
 "bb"

Thoughs:

1. similar to 647. Number of palindromic substring
2. O(n^2) with DP or center expansion, O(n) with Manacher’s algorithm
3. the number between left and right (exclusive) is "right - left - 1" and number from left and right (inclusive) is "right - left + 1"

Code (O (n^2) DP)

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        string ans = "";
        bool d[n][n] = {{false}}; 
        for(int i = n; i >= 0; i--){
            for(int j = i; j < n; j++){
                d[i][j] = (s[i] == s[j]) && (j - i < 3 || d[i+1][j-1]);
                if(d[i][j] && j - i + 1 > ans.length())
                    ans = s.substr(i,j - i + 1); // +1 since end exlusive 
            }
        }

        return ans;
    }
};

Code (O (n^2) without extra space)

class Solution {
public:
    string longestPalindrome(string s) {
        string ans = "";
        for(int i = 0; i < s.length() ; i ++){
            string s1 = extend(s,i,i), s2 = extend(s, i, i+1);

            if(s1.length() > ans.length()) ans = s1;
            if(s2.length() > ans.length()) ans = s2;
        }

        return ans;
    }

    string extend(string s, int left, int right){
        while(left >= 0 && right < s.length() && s[left] == s[right]){
            left--;
            right++;
        }
        return s.substr(left+1, right - left - 1);
    }
};

Code (O(n)) with Manacher's algorithm

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # For example, s = "abba", A = "@#a#b#b#a#$".
        A = '#'.join('@{}$'.format(s))
        Z = [0] * len(A)
        # print "%s\n%s"%(A,Z)
        center = right = 0
        for i in xrange(1, len(A) - 1):
        # get the palindrome numbers based on right boundary 
        # and mirror palindrome
            if i < right:
                Z[i] = min(right - i, Z[2 * center - i])
            #equivalent to: Z[i] = (right > i) and min(right - i, P[2*center - i])

            # explore the palindrome at current pivot
            while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
                Z[i] += 1

        # update right boundary
        if i + Z[i] > right:
            center, right = i, i + Z[i]

        maxlen, center = max((n, i) for i , n in enumerate(Z))
        return s[(center - maxlen)//2:(center + maxlen)//2 ]