class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
s = '#' + '#'.join(list(s)) + '#'
l = len(s)
p = [1 for x in range(l)]
mx = 0
id = 0
ans = 0
loc = 0
for i in range(l):
if mx > i:
j = 2 * id - i
p[i] = min(mx - i, p[j])
else:
p[i] = 1
kr = i + p[i]
kl = i - p[i]
#print(i, p[i])
while kr < l and kl >= 0:
if s[kr] == s[kl]:
p[i] += 1
kr += 1
kl -= 1
else:
break
if i + p[i] > mx:
mx = i + p[i]
id = i
if (ans < p[i]):
ans = p[i]
loc = i
str = s[loc - ans + 1: loc + ans].replace('#', '')
return str
