# C++ O(n) time solution, 8ms beats 80%, using Manacher algorithm

• This algorithm is hard to understand for me, not even mention to explain it......

``````string longestPalindrome(string s) {
if (s.empty()) return "";
string str(s.size() * 2 + 1, '#');
for (int i = 1; i < str.size(); i += 2) { str[i] = s[i / 2]; }
vector<int> P(str.size(), 0);
int maxLen = 1, j = 1, maxIndex = 1;
P[1] = 1;
for (int i = 2, size = str.size(); i < size; i++) {
int exBound = min(i, size - i - 1);
int exLen = min(P[2 * j - i], P[j] - i + j);
while (exLen < exBound && str[i + exLen + 1] == str[i - exLen - 1]) { exLen++; }
if (exLen > maxLen) {
maxIndex = i;
maxLen = exLen;
}
P[i] = exLen;
if (i + exLen > j + P[j]) { j = i; };
}
string res(maxLen, 0);
int middleIdx = maxLen / 2;
if (str[maxIndex] == '#') {
for (int i = 0; i < maxLen / 2; i++) {
res[middleIdx + i] = res[middleIdx - 1 - i] = str[maxIndex - i * 2 - 1];
}
} else {
for (int i = 0; i < maxLen / 2 + 1; i++) {
res[middleIdx + i] = res[middleIdx - i] = str[maxIndex - i * 2];
}
}
return res;
}``````

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