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 =  * 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