Leetcode 5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

The natural thought is to set every element as the center of palindromic string and see how far they can go, while there are many details to pay attention to. Also one by one checking does not take the advantage of some features of palindromic string and is hence not very efficient.

Actually a special algorithm was created to handle such problem: Manacher's Algorithm. See details here: https://en.wikipedia.org/wiki/Longest_palindromic_substring

The key thought is to use unrelated characters to fill the string and hence 'aba' and 'abba' can be solve in the same way; use mirror features to save calculations; care about interleaved palindromic strings.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {string} s
    # @return {string}
    def longestPalindrome(self, s):
        t = '$#' + '#'.join(s) + '#_'  
        # preprocess string to make it simple to use
        p = [0] * 2015
        LmaxH = maxCenter = currentCenter = rightBound = 0
        # LmaxH:Largest wanted string's length value's nearly half
        # maxCenter:the center of the wanted string
        for i in range(1, len(t) - 1):
        # $ and _ are not considered
            if rightBound > i:
                p[i] = min(rightBound - i, p[2*currentCenter - i])  
                # Use min value to make it safe
            else:
                p[i] = 1
            while t[i + p[i]] == t[i - p[i]]:
                p[i] += 1  
                # count length on the base of p[i], which saves a lot calculation
            if i + p[i] > rightBound:
                rightBound = p[i] + i
                currentCenter = i   # update rightBound and currentCenter
            if p[i] > LmaxH:
                LmaxH = p[i]
                maxCenter = i   # update max string information
        return s[maxCenter//2 - LmaxH//2 : maxCenter//2 - LmaxH//2 + LmaxH - 1]

Run Time: 180 ms