Manachar’s Algorithm - Longest palindromic substring in linear time

Problem

Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string

We have already seen simple O(n^2) solution here - [Longest Palindromic Substring](longest-palindromic-substring), but now lets look at Manacher’s Algorithm, which help us find the solution in linear time.

Examples

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Solution

Method 1 - Manacher's Algorithm

Intuition

1. Symmetry of Palindromes:
   • Palindromes exhibit symmetry: If a substring is a palindrome, there is a central point around which it’s symmetric.
2. Preprocessing:
   • To handle odd- and even-length palindromes uniformly, we preprocess the string by inserting special characters (e.g., '#') between every character in the string, including the boundaries. For example:
     • "babad" becomes "#b#a#b#a#d#".
3. Palindrome Radius:
   • For every position in the string, we calculate the radius of the palindrome centred at that position.
4. Optimised Expansion:
   • Instead of expanding at every character independently, we leverage the symmetry of palindromes and use previously computed results.

Approach

1. Preprocessing:
   • Transform the input string s by inserting special characters:
     • Original: "babad"
     • Transformed: "#b#a#b#a#d#"
   • This ensures all palindromes are odd-length, simplifying calculations.
2. Initialisation:
   • Create an auxiliary array p where p[i] stores the radius of the palindrome centred at position i.
   • Maintain two key variables:
     • center: The centre of the palindrome currently being expanded.
     • right: The right boundary (exclusive) of this palindrome.
3. Iterative Expansion:
   • For each index i in the transformed string:
     • If i falls within the current palindrome (i < right), mirror the palindrome radius at the symmetric point (mirror = 2*center - i) to initialise p[i].
     • Expand around i outward while the left and right characters match.
     • Update center and right if the newly expanded palindrome extends beyond the current right boundary.
4. Post-Processing:
   • The longest palindrome in the original string corresponds to the maximum radius in the p array.

Code

Java

class Solution {
    public String longestPalindrome(String s) {
        // Step 1: Preprocess the string
        StringBuilder sb = new StringBuilder();
        sb.append("#"); // Add boundary character to simplify palindrome handling
        for (char c : s.toCharArray()) {
            sb.append(c);
            sb.append("#");
        }
        String transformed = sb.toString();
        int n = transformed.length(); 
        
        // Step 2: Initialise auxiliary array
        int[] p = new int[n]; // Array to track palindrome radii
        int center = 0, right = 0; // Current center and right boundary of palindrome

        // Step 3: Expand around each character
        for (int i = 0; i < n; i++) {
            int mirror = 2 * center - i; // Mirrored index for `i`
            if (i < right) {
                p[i] = Math.min(p[mirror], right - i); // Initialise radius
            }
            
            // Try to expand the palindrome centered at `i`
            int a = i + p[i] + 1;
            int b = i - p[i] - 1;
            while (a < n && b >= 0 && transformed.charAt(a) == transformed.charAt(b)) {
                p[i]++;
                a++;
                b--;
            }
            
            // Update center and right boundary if palindrome expands beyond right
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }

        // Step 4: Find the longest palindrome
        int maxLen = 0, start = 0;
        for (int i = 0; i < n; i++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                start = (i - maxLen) / 2; // Map back to original string
            }
        }

        return s.substring(start, start + maxLen);
    }
}

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Step 1: Preprocess the string
        transformed = "#".join(f"#{s}#")
        n = len(transformed)
        
        # Step 2: Initialise auxiliary array
        p = [0] * n  # Array to track palindrome radii
        center = 0   # Current center of the palindrome
        right = 0    # Right boundary of the palindrome

        # Step 3: Expand around each character
        for i in range(n):
            mirror = 2 * center - i  # Mirrored index for `i`
            if i < right:
                p[i] = min(p[mirror], right - i)  # Initialise radius

            # Try to expand the palindrome centered at `i`
            a, b = i + p[i] + 1, i - p[i] - 1
            while a < n and b >= 0 and transformed[a] == transformed[b]:
                p[i] += 1
                a += 1
                b -= 1

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

        # Step 4: Find the longest palindrome
        max_len, center_index = max((p[i], i) for i in range(n))
        start = (center_index - max_len) // 2  # Map back to original string

        return s[start:start + max_len]

Example Walkthrough: "babad"

Preprocessing

• Transformed string: "#b#a#b#a#d#"

Initialisation

• p = [0] * len(transformed_string) (stores palindrome radii for each character).
• center = 0, right = 0.

Iteration Steps

1. For i = 0 ('#'):
   • Palindrome radius is 0 (boundary character).
2. For i = 1 ('b'):
   • Expand outward ('#b#' → radius = 1 at i).
   • Update center = 1, right = 2.
3. For i = 2 ('#'):
   • Palindrome radius is 0 (boundary character).
4. For i = 3 ('a'):
   • Expand outward ('#a#b#a#' → radius = 3 at i).
   • Update center = 3, right = 6.
5. For i = 4 ('#'):
   • Mirror previous calculations (p[4] = p[2] = 0).
6. … Continuing Calculation …:
   • You eventually compute the radii for all indices: p = [0, 1, 0, 3, 0, 1, 0, 5, 0, 1, 0, 3, 0, 1, 0].

Post-Processing

• Find the maximum radius in p (e.g., radius = 5 at i = 7).
• Map this back into the original string, removing special characters:
  • Longest palindrome is "bab" or "aba".

Complexity

• ⏰ Time complexity: O(n). The iterative expansion leverages precomputed results, ensuring linear complexity.
• 🧺 Space complexity: O(n). The transformed string and auxiliary array p both consume linear space.