Palindrome Patterns

Manacher's Algorithm

Finds the longest palindromic substring in O(n) by reusing information from previously computed palindromes. Uses the symmetry property: a palindrome within a larger palindrome has a mirror.

O(n)

How It Works

Manacher's algorithm finds the longest palindromic substring in true O(n) time. First, interleave a sentinel character (like '#') so every palindrome becomes odd-length, removing the odd/even case split. Then scan left to right maintaining the rightmost palindrome boundary seen so far. For each new center inside that boundary, its mirror position on the left has already been solved, so you initialize the new radius from the mirror's value instead of starting from zero.

Expansion only happens beyond the current right boundary, and that boundary only moves forward, so total expansion work is linear. This beats the O(n²) expand-around-center approach, though the bookkeeping is intricate enough that it is usually reserved for tight constraints.

Step-by-Step Visualization

Manacher's on 'aba' → '#a#b#a#'

P arraycomputing...

1/3

Code

Java

static int manacher(String s) {
  StringBuilder sb = new StringBuilder("#");
  for (char c : s.toCharArray()) { sb.append(c); sb.append('#'); }
  String t = sb.toString();
  int[] p = new int[t.length()];
  int center = 0, right = 0;

  for (int i = 0; i < t.length(); i++) {
    if (i < right) p[i] = Math.min(right - i, p[2 * center - i]);
    while (i - p[i] - 1 >= 0 && i + p[i] + 1 < t.length()
           && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) p[i]++;
    if (i + p[i] > right) { center = i; right = i + p[i]; }
  }
  int max = 0;
  for (int v : p) max = Math.max(max, v);
  return max;
}

Tips & Gotchas

1Insert separators between characters to handle even-length palindromes

2Reuse information from previously computed palindromes

3Maintain center and right boundary of the rightmost palindrome

Practice Problems

1Longest Palindromic Substring
2Palindromic Substrings
3Maximum Number of Non-overlapping Palindrome Substrings

About the Palindrome Patterns Pattern

A palindrome reads the same forwards and backwards. The core techniques: expand from the center outward to find palindromes, or use DP to check if substrings are palindromes.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

Longest Substring Without Repeating Characters
Valid Anagram
Longest Palindromic Substring
Minimum Window Substring
Group Anagrams

Frequently Asked Questions

Is Manacher's algorithm expected in interviews?

Rarely. Most interviewers accept the O(n²) expand-around-center solution, and mentioning that Manacher's achieves O(n) earns credit without requiring a flawless implementation. Learn it fully if you are targeting competitive programming or the follow-up explicitly demands linear time.

What does inserting '#' between characters actually accomplish?

It converts every palindrome, odd or even, into an odd-length palindrome in the transformed string, so a single center-expansion rule covers both cases. The palindrome radius in the transformed string also directly equals the palindrome length in the original.