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 accordingly.
• If the expanded palindrome extends beyond the current right boundary, update the center and right variables.
• If the current palindrome is longer than the previously recorded longest palindrome, update max_len and center_index.
• Convert the center position from the transformed string back to the corresponding starting index in the original string.
• Return the longest palindromic substring using the calculated starting index and maximum length.

Complexity

• Time complexity: O(n)
  Each character in the transformed string is expanded at most once beyond the current right boundary. Thanks to the mirror optimization, redundant comparisons are eliminated, giving an overall linear runtime.

• Space complexity: O(n)
  Additional space is used for the transformed string and the palindrome radius array (p).

Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        # Transform the string to handle even and odd palindromes uniformly.
        # Example:
        # "abba" -> "^#a#b#b#a#$"
        t = "^#" + "#".join(s) + "#$"
        n = len(t)

        # p[i] = radius of palindrome centered at i
        p = [0] * n

        center = 0
        right = 0

        max_len = 0
        center_index = 0

        for i in range(1, n - 1):

            mirror = 2 * center - i

            # Use previously computed palindrome information
            if i < right:
                p[i] = min(right - i, p[mirror])

            # Expand around center i
            while t[i + p[i] + 1] == t[i - p[i] - 1]:
                p[i] += 1

            # Update center and right boundary
            if i + p[i] > right:
                center = i
                right = i + p[i]

            # Track the longest palindrome
            if p[i] > max_len:
                max_len = p[i]
                center_index = i

        # Convert index in transformed string back to original string
        start = (center_index - max_len) // 2

        return s[start:start + max_len]