```
``````
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
#Manacher Algo O(n)
n = len(s)
center = right = 0
T = self.preprocess(s)
# Below list track length of pallindrome at each center
P = [0]*len(T)
for i in xrange(1, len(T) - 1):
i_mirror = 2 * center - i
if i < right:
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]]
def preprocess(self, s):
if not s:
return ['^','$']
T = ['^']
for c in s:
T += ['#',c]
T += ['#','$']
return T
```