Mastering Manacher’s Algorithm: Find the Longest Palindromic Substring in O(N)

Finding the longest palindromic substring is a classic yet tricky problem that frequently appears in technical interviews. It asks for the longest substring of a given string that reads the same forward and backward, e.g., "level", "madam", "abba". For example, for the string "babad", the longest palindromic substring can be "bab" or "aba".

Although there are many ways to solve this problem, Manacher’s algorithm is undoubtedly the most elegant and efficient.

Manacher’s algorithm was proposed by Glenn Manacher in 1975, originally to list all palindromes that start at each position of a length‑n string in O(n) time. Compared with the brute‑force O(n³) solution or the O(n²) dynamic programming approach, Manacher’s algorithm is extremely fast, and mastering it will make you stand out in interviews!

Modify Input String

The first step of Manacher’s algorithm is to modify the input string: insert a special non‑letter character (e.g., # ) at the beginning, between every two characters, and at the end.

<code>def longest_palindrome(s: str) -> str:
    s_prime = "#" + "#".join(s) + "#"
    n = len(s_prime)
    """ 
    s = hello
    s_prime = #h#e#l#l#o#
    n = 11

    s = hi
    s_prime = #h#i#
    n = 5
    """
</code>

This ensures that all potential palindromes in the new string have odd length, which simplifies handling.

Initialization

Before the main loop, we need to understand the following variables:

<code>def longest_palindrome(s: str) -> str:
    s_prime = "#" + "#".join(s) + "#"
    n = len(s_prime)
    palindrome_radii = [0] * n
    center = right_boundary = 0
</code>

palindrome_radii

An array that stores, for each index of the transformed string s_prime , the radius of the palindrome centered at that index (i.e., the number of characters the palindrome expands to the left and right).

The radius also equals the length of the palindrome without the # characters.

center

The index of the center of the rightmost palindrome found so far in s_prime .

When the palindrome centered at the current index extends beyond the current right_boundary , we update center .

right_boundary

The farthest right boundary (index) reached by any palindrome discovered in s_prime so far.

If a palindrome centered at the current index reaches farther than the previous right_boundary , we update right_boundary .

High‑Level Understanding

The algorithm can be divided into three cases:

Expand only

Expand + update center and right_boundary

Mirror + expand + update center and right_boundary

We illustrate each case with a simple example using the string "ABCBABCDD" .

Case 1: Expand Only

<code>while (i + 1 + palindrome_radii[i] < n
       and i - 1 - palindrome_radii[i] >= 0
       and s_prime[i + 1 + palindrome_radii[i]] == s_prime[i - 1 - palindrome_radii[i]]):
    palindrome_radii[i] += 1
</code>

This case occurs only when i = 0 . We compare the character at the current index with its neighbor and update palindrome_radii accordingly.

As shown, palindrome_radii[0] remains 0 because there is no character to the left of index 0 in s_prime , so expansion is impossible.

Case 2: Expand + Update center and right_boundary

<code>while (i + 1 + palindrome_radii[i] < n
       and i - 1 - palindrome_radii[i] >= 0
       and s_prime[i + 1 + palindrome_radii[i]] == s_prime[i - 1 - palindrome_radii[i]]):
    palindrome_radii[i] += 1

if i + palindrome_radii[i] > right_boundary:
    center = i
    right_boundary = i + palindrome_radii[i]
</code>

When expanding from the current index, the palindrome may exceed the current right_boundary . In that case we update center to the current index and set right_boundary to the new farthest point.

Case 3: Mirror + Expand + Update center and right_boundary

<code>mirror = 2 * center - i

if i < right_boundary:
    palindrome_radii[i] = min(right_boundary - i, palindrome_radii[mirror])

while (i + 1 + palindrome_radii[i] < n
       and i - 1 - palindrome_radii[i] >= 0
       and s_prime[i + 1 + palindrome_radii[i]] == s_prime[i - 1 - palindrome_radii[i]]):
    palindrome_radii[i] += 1

if i + palindrome_radii[i] > right_boundary:
    center = i
    right_boundary = i + palindrome_radii[i]
</code>

This case reveals the core of Manacher’s algorithm. The “mirror” concept exploits the symmetry of palindromes, allowing us to reuse previously computed radii and avoid redundant expansions.

Assume the palindrome centered at center covers the range [center - palindrome_radii[center], center + palindrome_radii[center]] . If index i lies within this range, the characters symmetric around the center should yield the same palindrome substrings when considered as centers.

However, the mirror index may point to a palindrome that extends beyond the current right_boundary , and we cannot assume that index i is also verified. Therefore we take the minimum of right_boundary - i and palindrome_radii[mirror] as the initial radius.

Subsequent images illustrate how the algorithm progresses on the example string.

Summary

We have achieved O(n) time complexity! Compared with the brute‑force method, Manacher’s algorithm runs in linear time because it reuses previously computed information instead of expanding from scratch each time, eliminating redundant work.

Now that we have dissected Manacher’s algorithm, its clever use of mirroring, expansion, and optimization should be easy to understand. What once seemed a mysterious linear‑time solution is simply a smart combination of symmetry and careful bookkeeping.

Whether you are preparing for interviews, reviewing algorithms, or just love elegant solutions, you now have a clear grasp of how Manacher’s algorithm works.

Mastering this knowledge makes finding the longest palindromic substring in O(n) time a breeze!

Full Code

<code>class Solution:
    def longestPalindrome(self, s: str) -> str:
        s_prime = "#" + "#".join(s) + "#"
        n = len(s_prime)
        palindrome_radii = [0] * n
        center = right_boundary = 0

        for i in range(n):
            mirror = 2 * center - i

            if i < right_boundary:
                palindrome_radii[i] = min(right_boundary - i, palindrome_radii[mirror])

            while (i + 1 + palindrome_radii[i] < n
                   and i - 1 - palindrome_radii[i] >= 0
                   and s_prime[i + 1 + palindrome_radii[i]] == s_prime[i - 1 - palindrome_radii[i]]):
                palindrome_radii[i] += 1

            if i + palindrome_radii[i] > right_boundary:
                center = i
                right_boundary = i + palindrome_radii[i]

        max_length = max(palindrome_radii)
        center_index = palindrome_radii.index(max_length)
        start_index = (center_index - max_length) // 2
        longest_palindrome = s[start_index : start_index + max_length]

        return longest_palindrome
</code>