':type s: str
:rtype: str'

def longestPalindrome(self, s):

    def preProcess(s):
        if (not s):
            return ['^', '$']
        T = ['^']
        for c in s:
            T += ['#', c]
        T += ['#', '$']
        return T
    T = preProcess(s)
    P = ([0] * len(T))
    (center, right) = (0, 0)
    for i in xrange(1, (len(T) - 1)):
        i_mirror = ((2 * center) - i)
        if (right > i):
            P[i] = min((right - i), P[i_mirror])
        else:
            P[i] = 0
        while (T[((i + 1) + P[i])] == T[((i - 1) - P[i])]):
            P[i] += 1
        if ((i + P[i]) > right):
            (center, right) = (i, (i + P[i]))
    max_i = 0
    for i in xrange(1, (len(T) - 1)):
        if (P[i] > P[max_i]):
            max_i = i
    start = (((max_i - 1) - P[max_i]) / 2)
    return s[start:(start + P[max_i])]
