# C++ linear solution O(n) time

• Manacher's algorithm
https://en.wikipedia.org/wiki/Longest_palindromic_substring

``````   class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;

string st(2 * s.size() + 1, '*'); // create new string, we simulate odd case palindrom in all cases
for (int i = 0; i < s.size(); ++i) {
st[2 * i + 1] = s[i];
}

vector<int> pal(st.size());
int pal1 = 0, left = 0, right = 0;
for (int i = 0; i < st.size(); ++i) {
if (i < right) {
int mirror = 2 * pal1 - i;
if (pal[mirror] < mirror - left) {
pal[i] = pal[mirror];
continue;
}
if (pal[mirror] > mirror - left) {
pal[i] = mirror - left;
continue;
}
if (pal[mirror] == mirror - left) {
pal[i] = mirror - left;
}
} else {
right = i;
}
while (right + 1 < st.size() && right - 2 * pal[i] - 1 >= 0 &&
st[right + 1] == st[right - 2 * pal[i] - 1]) {
right++;
pal[i]++;
}
left = right - 2 * pal[i];
pal1 = i;
}
auto it = max_element(pal.begin(), pal.end());

string answ_z, answ;
answ_z = st.substr(it - pal.begin() - *it, 2 * *it + 1);
for (int i = 0; i < answ_z.size(); ++i) { // convert answer to correct form
if (answ_z[i] != '*') {
answ += answ_z[i];
}
}
return answ;
}
};``````

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