advanced-strings • Expert

Manacher's Algorithm: Longest Palindromic Substring in O(N)

Manacher's algorithm finds the longest palindromic substring in strictly linear O(N) time by inserting virtual delimiters to unify odd/even lengths and exploiting palindromic symmetry around a center.

Intuitive Mental Model

The Butterfly Wings: If you know the left wing has a 3cm yellow spot 2cm from the spine, the right wing must have the exact same spot without measuring it again.

C / TypeScript ImplementationHardware & Algorithmic Standard

function longestPalindrome(s: string): string {
  const t = "^#" + s.split("").join("#") + "#$";
  const p = new Array(t.length).fill(0);
  let C = 0, R = 0;

  for (let i = 1; i < t.length - 1; i++) {
    const iMirror = 2 * C - i;
    if (R > i) p[i] = Math.min(R - i, p[iMirror]);
    while (t[i + 1 + p[i]] === t[i - 1 - p[i]]) p[i]++;
    if (i + p[i] > R) {
      C = i;
      R = i + p[i];
    }
  }
  // Extract maximum radius palindrome...
  return s;
}

Key Architectural Takeaways

•Unifies Odd & Even Palindromes: "#a#b#a#" handles both 3-letter and 4-letter palindromes uniformly.
•Linear O(N) Time: Replaces standard O(N^2) center expansion.

Common Coding Mistake

Forgetting to map delimited indices back to original string coordinates.

Optimal Solution

Original start index = (center - maxRadius) / 2.

Next: Boyer-Moore Search: Bad Character & Good Suffix Rules