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 &str) {
string odd_matching_str(1 + str.size() * 2 + 2, '#');
*odd_matching_str.begin() = '!';
*odd_matching_str.rbegin() = '@';
for (int i = 0, j = 2; i < str.size(); ++i, j += 2) {
odd_matching_str[j] = str[i];
}
vector<int> radius(odd_matching_str.size());
int max_radius_center = 0, max_radius = 0;
for (int i = 1, center = 0, border = 0; i < odd_matching_str.size(); ++i) {
int mirror = 2 * center - i;
radius[i] = border > i ? min(border - i, radius[mirror]) : 0;
while (odd_matching_str[i + radius[i] + 1] == odd_matching_str[i - radius[i] - 1]) {
++radius[i];
}
if (i + radius[i] > border) {
center = i;
border = i + radius[i];
}
if (radius[i] > max_radius) {
max_radius_center = i;
max_radius = radius[i];
}
}
int first_palindrome_index = (max_radius_center - max_radius) / 2;
return string(
str.begin() + first_palindrome_index,
str.begin() + first_palindrome_index + max_radius);
}
};