Spent some time understanding how this Manacher's algorithm works. This is a O(n) version with linear space consumption.

We first transform the string 'aba' -> '#a#b#a#'

The value in dp represents the longest step expand from the center i, so that the longest palindrome centered at i should be dp[i]-1.

for each i, the center is the equivalent to max(dp[:i])

```
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
s = '#' + '#'.join(s) + '#'
dp = [1] * len(s)
center = 0
for i, _ in enumerate(s):
if dp[center] + center > i:
dp[i] = min(dp[2*center-i], dp[center]+center-i)
while i - dp[i] >= 0 and i + dp[i] < len(s) and s[i-dp[i]] == s[i+dp[i]]:
dp[i] += 1
if dp[i] > dp[center]:
center = i
return s[center-dp[center]+2:center+dp[center]:2]
```

I read the post from this link for the problem: http://articles.leetcode.com/longest-palindromic-substring-part-ii/. And this one is even better if you read Chinese: https://www.felix021.com/blog/read.php?2040