O(N) Manacher's Algorithm with Mirror Boundary Optimization

Intuition Manacher's Algorithm leverages the symmetry of palindromes to avoid redundant comparisons. Instead of treating odd- and even-length palindromes separately, the input string is transformed by inserting a special character (#) between every character and adding sentinel characters (^ and $) at both ends. This allows every palindrome to be treated as an odd-length palindrome. While traversing the transformed string, the algorithm maintains the center and right boundary of the rightmost palindrome found so far. For each position, it uses the palindrome information from its mirror position (with respect to the current center) to initialize the palindrome radius, significantly reducing unnecessary expansions. Only when the palindrome reaches beyond the current right boundary is additional expansion performed. This optimization ensures that every character is expanded at most a constant number of times, resulting in linear time complexity. Approach Handle the edge case by returning an empty string if the input string is empty. Transform the input string by inserting # between every character and adding sentinel characters (^ and $) at both ends to treat odd- and even-length palindromes uniformly. Create a palindrome radius array p, where p[i] stores the radius of the palindrome centered at index i in the transformed string. Initialize the variables center and right to represent the center and right boundary of the current rightmost palindrome. Initialize max_len and center_index to keep track of the longest palindrome found during traversal. Traverse the transformed string from left to right, ignoring the sentinel characters. Compute the mirror index of the current position using the current palindrome's center. If the current index lies within the current right boundary, initialize its palindrome radius using the previously computed mirror information. Expand around the current center while the characters on both sides are equal, increasing the palindrome radius