5. Longest Palindromic Substring
1. Description
Given a string s, return the longest palindromic substring in s.
2. Example
Example 1
Input: s = “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2
Input: s = “cbbd”
Output: “bb”
Example 3
Input: s = “a”
Output: “a”
Example 4
Input: s = “ac”
Output: “a”
3. Constraints
- 1 <= s.length <= 1000
- s consist of only digits and English letters (lower-case and/or upper-case),
4. Solutions
Manacher
n = str.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
string longestPalindrome(const string &s) {
string str(s.size() * 2 + 3, '#');
str.front() = '@';
str.back() = '$';
for (int i = 0, j = 2, n = s.size(); i < n; ++i, j += 2) {
str[j] = s[i];
}
const int n = str.size();
vector<int> p(n, 0);
int center = 0, right = 0;
int max_center = 0, max_radius = 0;
for (int i = 1; i < n - 1; ++i) {
int mirror = 2 * center - i;
if (i < right) {
p[i] = min(right - i, p[mirror]);
}
while (str[i + p[i] + 1] == str[i - p[i] - 1]) {
++p[i];
}
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
if (p[i] > max_radius) {
max_radius = p[i];
max_center = i;
}
}
int start = (max_center - max_radius) / 2;
return s.substr(start, max_radius);
}
};