Longest Palindromic Substring

Question: 5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Initial Thought:

I need to find the longest palindromic substring. A common approach is to expand around each character as a potential center.

Improved Approach: Manacher's Algorithm

For an even more efficient $O(n)$ solution, we can use Manacher's Algorithm.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";

        // Transform s: insert '#' between chars and add '^' at start and '$' at end
        string t = "^";
        for (char c : s) {
            t += "#" + string(1, c);
        }
        t += "#$";

        int n = t.length();
        vector<int> P(n, 0); // palindrome radius array
        int center = 0, right = 0;

        for (int i = 1; i < n - 1; i++) {
            int mirror = 2 * center - i;

            if (i < right)
                P[i] = min(right - i, P[mirror]);

            // Expand around center i
            while (t[i + 1 + P[i]] == t[i - 1 - P[i]])
                P[i]++;

            // Update center and right boundary
            if (i + P[i] > right) {
                center = i;
                right = i + P[i];
            }
        }

        // Find the maximum palindrome length
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < n - 1; i++) {
            if (P[i] > maxLen) {
                maxLen = P[i];
                centerIndex = i;
            }
        }

        int start = (centerIndex - maxLen) / 2; // map back to original string
        return s.substr(start, maxLen);
    }
};

This video helped me understand the Manacher's Algorithm:

Manacher's Algorithm is definitely tricky to wrap your head around at first, but its efficiency in handling both even and odd length palindromes is fascinating. Once you understand how the mirrored indices work, it becomes much clearer.