Based on **Manacher algorithm** on Wiki and a brilliant article here http://articles.leetcode.com/longest-palindromic-substring-part-ii.

```
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# make it okay for both odd and even cases
T = "^#" + "#".join(list(s)) + "#$"
n = len(T)
P = [0] * n
# C and R are center and right boundary of current farest palindrome
C = R = 0
for i in range(1, n-1):
P[i] = min(R-i, P[2*C-i]) if R > i else 0
# check palindrome only for possible candidate, key idea why it's O(n)
if P[i] + i >= R:
while T[i-1-P[i]] == T[i+1+P[i]]:
P[i] += 1
# update C and R
C, R = i, i + P[i]
L, C = max((x, j) for j, x in enumerate(P))
return s[(C - L) >> 1 : (C + L) >> 1]
```