# 6ms Solution using Manacher's Algorithm, Linear Time O(n), C++

• Please wiki Mandacher's algorithm for detailed explanation.

``````class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return s;
if (s.size()==1) return s;
if (s.size()==2) return (s[0]==s[1])? s:s.substr(0, 1);

// dynamic programming
vector<int> dp(s.size()*2+1, 0); // contains longest palindrome length
dp[1] = 1;
int j, k; // j: mirror to the center, k: span of current palindrome
int center = 1, end = 2;

for(int i=2;i<dp.size();i++){
if (i<end) {
j = center-(i-center); // j = i's mirror to the center
if (dp[j]+i<end) dp[i] = dp[j]; // case 1,
else { // case 2
k = end-i;
while((i+k)<dp.size() && (i-k)>=0 && !((i+k)%2==1 && (s[(i+k)/2] != s[(i-k)/2]))) dp[i] = k++;
end = i+dp[i], center = i; // update new end and new center
}
} else { // case 3
k=0;
while((i+k)<dp.size() && (i-k) >= 0 && !((i+k)%2==1 && (s[(i+k)/2] != s[(i-k)/2]))) dp[i] = k++;
end = i+dp[i], center = i; // update new end and new center
}
}

auto maxIter = max_element(dp.begin(), dp.end());
int maxlength = *maxIter;
int maxind = distance(dp.begin(), maxIter);
return s.substr((maxind-maxlength)/2, maxlength);

}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.