manachers

class Solution:

    def longestPalindrome(self, s: str) -> str:

        n = len(s)
        if n < 1:
            return ''

        tmp = list()
        tmp.append('')
        for c in s:
            tmp.append(c)
        tmp.append('')

        T = '#'.join(tmp) # 'abc' -> '#a#b#c#'
        N = len(T)
        P = [0] * N

        max_rad = 0
        max_rad_ci = 0

        C = 0
        R = -1
        for i in range(N):

            if i < R:
                rad = min(P[C*2-i], R-i)
            else:
                rad = 0

            while i-rad >= 0 and i+rad < N and T[i-rad] == T[i+rad]:
                rad += 1

            P[i] = rad

            if rad > max_rad:
                max_rad = rad
                max_rad_ci = i

            if (i + rad - 1) > R:
                C = i
                R = i + rad - 1

        start = max_rad_ci - max_rad + 1
        end = max_rad_ci + max_rad
        longest_palindrome = T[start:end]
        return longest_palindrome.replace('#', '')