Find the longest palindromic substring in O(n) time using Manacher's algorithm.
Input: s="babad" → Output: "bab"
Input: s="cbbd" → Output: "bb"
Transform string with separators. Use center expansion with pre-computed radius array to avoid redundant work.
- Transform s to T: "#a#b#a#b#" format
- Compute p[i] = radius of palindrome centered at i using mirror property
- Track center c and right boundary r
- For each center, expand while T[i+j]==T[i-j]
- Return longest palindrome from T
public String longestPalindrome(String s) {
String T = "#" + String.join("#", s.split("")) + "#";
int n = T.length();
int[] p = new int[n];
int c = 0, r = 0, maxLen = 0, center = 0;
for (int i = 0; i < n; i++) {
int mirror = 2 * c - i;
if (i < r) p[i] = Math.min(r - i, p[mirror]);
while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && T.charAt(i+p[i]+1) == T.charAt(i-p[i]-1))
p[i]++;
if (i + p[i] > r) { c = i; r = i + p[i]; }
if (p[i] > maxLen) { maxLen = p[i]; center = i; }
}
int start = (center - maxLen) / 2;
return s.substring(start, start + maxLen);
}
- Time Complexity: O(n)
- Space Complexity: O(n)