Algo: Manacher's Algorithm for Palindromes

Finding the longest palindromic substring is a classic problem that seems deceptively simple. A naive check of every possible substring would take $O(n^3)$ time, and even an improved center-expansion approach runs in $O(n^2)$. Manacher's algorithm solves this optimally by finding all maximal palindromes centered at each position in a string in linear $O(n)$ time. Its power lies in a clever transformation and an ingenious exploitation of palindrome symmetry to avoid redundant computations, making it a cornerstone technique for competitive programming and text analysis.

Transforming the Problem: Handling Even and Odd Lengths

The first challenge in any palindrome algorithm is handling substrings of both even and odd lengths uniformly. A center-expansion approach for an odd-length palindrome, like "racecar", expands from a single character. For an even-length palindrome like "abba", you must expand from the space between characters. This complicates logic and implementation.

Manacher's algorithm solves this by inserting a dummy character (commonly '#') between every character in the original string and at the ends. For example, the string "abba" transforms into "^#a#b#b#a#" (where '^' and '' are sentinels to prevent boundary checks). This transformation guarantees that every palindrome in the new string is odd-length, centered on an actual character or a '#'. The center of the original even palindrome "abba" becomes the '#' between the two 'b's. After processing, we can easily convert radii back to the original string's indices.

Leveraging Symmetry: The Core Insight

The heart of Manacher's algorithm is its use of previously computed information to accelerate new computations. The algorithm maintains an array P (or radius), where P[i] stores the radius (half-length) of the palindrome centered at position i in the transformed string. It also tracks C, the center of the current rightmost palindrome, and R, its right boundary.

When processing a new center i, we use the symmetric property of palindromes around C. The mirror of i is mirror = 2*C - i. Because the palindrome centered at C spans from C-R to R, we know that the palindrome at mirror is at least contained within this large palindrome. Therefore, we can initialize: P[i] = min(R - i, P[mirror]).

This is the critical optimization. Instead of starting expansion from a radius of 0, we can jump-start P[i] with this minimum value. We only need to perform character comparisons for expansion beyond this guaranteed radius. This reuse of information is what transforms the algorithm from $O(n^2)$ to $O(n)$, as each character is successfully compared at most a constant number of times—once when it's inside R (via the min operation) and potentially once more when it expands R itself.

The Algorithm Step-by-Step

Let's walk through the algorithm's flow with the transformed string S.

1. Initialize: Create array P of length n (length of transformed string) filled with zeros. Set center C = 0 and right boundary R = 0.
2. Loop through each index i from 1 to n-2.
3. Get Mirror & Jump-start: Calculate mirror = 2*C - i. Set P[i] = (R > i) ? min(R - i, P[mirror]) : 0.

• If i is within the current right boundary R, we use the symmetric property.
• If i is outside R, we initialize P[i] to 0.

1. Expand: While the characters at S[i + 1 + P[i]] and S[i - 1 - P[i]] are equal, increment P[i]. This attempts to expand the palindrome centered at i.
2. Update Center and Boundary: If the palindrome centered at i expands past R, update C = i and R = i + P[i]. This means we have found a new, farther-reaching palindrome to use as our symmetry reference.
3. Extract Original Indices: After building P, the longest palindrome in the original string corresponds to the maximum value in P. The center index i and radius P[i] in the transformed string can be converted back. The original length is P[i] (the radius in the transformed string). The original start index is (i - P[i]) / 2.

This process ensures every character is used as a center, and the expansion step is amortized constant time due to the constant forward movement of R.

Application: Longest Palindromic Substring

Manacher's algorithm is the definitive solution for the Longest Palindromic Substring problem. By finding max(P[i]) and its corresponding center i, you have directly located the answer. The algorithm provides much more—it gives you the lengths of all maximal palindromes centered at every position in linear time. This comprehensive data is useful for more complex problems, such as counting all palindromic substrings or finding palindromic structures in DNA sequences.

The transformed string technique ensures you find both even and odd candidates. For example, if the maximum P[i] is centered on a '#', the original palindrome is even-length. If centered on an original character, it's odd-length. The conversion formula handles this seamlessly.

Common Pitfalls

1. Incorrect Transformation or Index Conversion: A frequent error is mishandling the sentinel characters or the index math when converting between the transformed and original string. Always use a consistent transformation pattern (e.g., "^#" + s.split('').join('#') + "#$") and derive the conversion formulas carefully. Test with simple even and odd cases like "a" and "aa".
2. Forgetting to Update C and R: The algorithm's efficiency depends on maintaining the rightmost palindrome (C and R). A common mistake is to update C to i every time, instead of only when i + P[i] > R. Updating only when the boundary expands is crucial for correctness and performance.
3. Off-by-One Errors in the Expansion Loop: The expansion condition S[i + 1 + P[i]] == S[i - 1 - P[i]] must match your transformed string's indices. Using <= or incorrect offsets will lead to infinite loops or incorrect radii. Remember that P[i] is the current known radius, and you are checking the next character beyond it.
4. Misunderstanding the min(R - i, P[mirror]) Assignment: This line is the optimization. Using P[mirror] directly when i is within R is safe because of symmetry. Using R - i is necessary because the palindrome at mirror may extend beyond the left boundary of the large palindrome centered at C; its symmetry cannot be guaranteed outside R. Taking the minimum ensures we only use the part we know is identical.

Summary

• Manacher's algorithm finds all maximal palindromic substrings in $O(n)$ linear time by exploiting palindrome symmetry to avoid redundant character comparisons.
• The transformed string technique (inserting '#' between characters) handles both even- and odd-length palindromes uniformly by converting them all into odd-length palindromes in the new string.
• The algorithm maintains a radius array P and a reference palindrome defined by its center C and right boundary R. For a new center i, it jump-starts P[i] using the minimum of (R - i) and the radius of i's mirror, then expands only as needed.
• It is the optimal solution for the longest palindromic substring problem and provides a complete palindrome-length map for the entire string.
• Careful implementation is required to correctly manage the transformed string indices, update the reference palindrome only when its boundary expands, and avoid off-by-one errors during expansion.