Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 225 ยท Strings

Palindromic Substrings and Manacher

Find palindromic substrings in Python. Compare brute force O(n^3), expand around center O(n^2) and Manacher's linear algorithm with traces and complexity.

A palindrome reads the same forwards and backwards: level, noon, a. Palindromes appear in interview questions, in DNA analysis (reverse-complement symmetry) and as a testing ground for string techniques. Two questions come up again and again:

  1. What is the longest palindromic substring of a string?
  2. How many palindromic substrings does it contain?

You already met checking a single palindrome in Classic String Problems. Here we scale up. We start with a cubic brute force, improve it to quadratic with the "expand around center" idea, and finish with Manacher's algorithm, which answers both questions in O(n) time by reusing mirror information, much like the Z-algorithm reuses its Z-box.

Every palindrome has a center

A palindrome is symmetric around its middle. For odd length the middle is a character; for even length it is the gap between two characters.

TEXT
odd:   r a c e c a r      center = 'e' (index 3)
even:  a b b a            center = gap between index 1 and 2

A string of length n therefore has 2n - 1 possible centers: n characters and n - 1 gaps. If you know the center, you can find the biggest palindrome around it by stretching outwards while the two end characters agree.

Brute force: check every substring

There are about nยฒ/2 substrings, and checking each one costs up to O(n), so the total is O(nยณ).

Python Brute force longest palindrome

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For "babad" both "bab" and "aba" are valid answers of length 3; our loop keeps the first one it finds. That is fine: unless a problem demands a specific one, any longest palindrome is accepted.

Expand around center: O(nยฒ)

Instead of testing substrings, test centers. For each of the 2n - 1 centers, expand while s[left] == s[right]. Each expansion costs at most O(n), so the total is O(nยฒ) time and O(1) extra space. This is the version to write in most interviews: short, clear and fast enough for n in the low thousands.

Python Expand around center

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For "aaa" there are 6 palindromic substrings: a, a, a (three single letters), aa, aa and aaa. Note that we count each position of a substring separately, which is the usual convention.

The worst case for expand-around-center is a string such as "aaaa...a", where every center expands almost to the edges, giving ฮ˜(nยฒ). Can we avoid re-doing the same comparisons for neighboring centers? Yes, that is exactly Manacher's insight.

Manacher's algorithm

Step 1: make every palindrome odd

Having to treat odd and even centers separately is annoying. Insert a separator # between every pair of characters and at both ends:

TEXT
s = "abba"     ->  t = "#a#b#b#a#"
s = "aba"      ->  t = "#a#b#a#"

Now every palindrome of s becomes an odd palindrome in t, centered either on a letter or on a #. A string of length n becomes length 2n + 1.

Step 2: the radius array

Let p[i] be the radius of the longest palindrome in t centered at i, counted in characters on each side. A neat fact: p[i] equals the length of the corresponding palindrome in the original string.

TEXT
t:   #  a  #  b  #  b  #  a  #
i:   0  1  2  3  4  5  6  7  8
p:   0  1  0  1  4  1  0  1  0

p[4] = 4 -> "#a#b#b#a#" is a palindrome around the middle '#' -> "abba" has length 4

Step 3: mirror and the rightmost palindrome

Keep the palindrome that reaches furthest right: its center c and right edge r = c + p[c]. For a new index i with i < r, its mirror across c is j = 2c - i. Everything inside the big palindrome is symmetric, so what we know about j carries over to i:

TEXT
 left edge            c              r
    [ ....  j ....... c ....... i .... ]
              mirror -----------> i
    p[i] >= min(p[j], r - i)
  • If the palindrome at the mirror j lies completely inside the big one (p[j] < r - i), then p[i] = p[j] exactly, with no comparisons.
  • If it touches or crosses the edge, we only know p[i] >= r - i, so we start from there and try to expand past r.

Each expansion step pushes r to the right, and r never moves left, so all the expansions together cost O(n). The total is O(n) time, O(n) space.

Python Manacher's algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two formulas are worth memorising:

  • Longest palindrome: if p[i] is the largest radius, the substring starts at (i - p[i]) // 2 in s and has length p[i].
  • Number of palindromic substrings: each center contributes (p[i] + 1) // 2 palindromes (the radius counts # characters too, and we round up so that odd and even centers both work).

A trace of Manacher's mirror step

Take s = "abaaba", so t = "#a#b#a#a#b#a#" (13 characters, indexes 0 to 12). The loop reaches index 6, the # between the two middle a characters. Expanding from scratch there gives the biggest palindrome: all of abaaba, with p[6] = 6, so center = 6 and right = 12.

TEXT
t:   #  a  #  b  #  a  #  a  #  b  #  a  #
i:   0  1  2  3  4  5  6  7  8  9 10 11 12
p:   0  1  0  3  0  1  6  ?  ?  ?  ?  ?  ?

Now index 7 has mirror 2*6 - 7 = 5, with p[5] = 1, and right - i = 5. Since 1 < 5, p[7] = 1 is copied with zero extra comparisons. Index 9 has mirror 3 with p[3] = 3 and right - i = 3; the mirror touches the edge, so the algorithm starts from 3 and tests whether it can extend past right (it cannot, because the string ends). Run the code above to see the full array.

Python Counting comparisons: expand versus Manacher

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Doubling n roughly quadruples the expand-around-center count (quadratic) but only roughly doubles Manacher's (linear). That gap becomes enormous for strings with 100,000 characters.

More palindrome problems

Longest palindromic subsequence (letters need not be adjacent) is a different problem: it is solved with dynamic programming in O(nยฒ), not with these methods.

Shortest palindrome by adding characters in front. Find the longest palindromic prefix of s; then reverse the remaining part and put it in front. A neat way: compute the prefix function / Z array of s + "#" + reversed(s).

Palindrome partitioning (cut a string into the fewest palindromes) uses a palindrome lookup table, which you can fill with expand-around-center.

Python Shortest palindrome by prepending

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Method Time Extra space
Check every substring O(nยณ) O(n) for slices
Expand around center O(nยฒ) O(1)
Dynamic programming table O(nยฒ) O(nยฒ)
Manacher O(n) O(n)

Common mistakes

  • Forgetting even-length palindromes in expand-around-center. Always try (c, c) and (c, c + 1).
  • Off-by-one on slice ends, because expand returns an exclusive right end.
  • Letting the separator clash. Padding with # is safe even if s contains #, because a separator is only ever compared with another separator at mirrored positions. Versions that add sentinels such as ^ and $ at the ends need characters that never occur in s.
  • Counting radius as length in t. The palindrome length in the original string is p[i], not 2*p[i] + 1.
  • Mixing up subsequence and substring. Substrings are contiguous; subsequences are not.

When to use which

Use expand-around-center when n is small to moderate and you want simple code. Use Manacher when n is large (hundreds of thousands) or when you need all palindromic radii in one pass. Use DP for subsequences and partitioning questions.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many possible centers does a string of length n have for palindromes of odd and even length together?

    There are n character centers (odd palindromes) and n - 1 gaps between characters (even palindromes).
  2. 2. What is the time complexity of the expand-around-center method?

    There are 2n - 1 centers and each expansion can take O(n) steps, for example on a string of identical letters.
  3. 3. Why does Manacher's algorithm insert a separator between all characters?

    With separators, the even palindrome abba becomes #a#b#b#a#, which has a single center character.
  4. 4. For an index i inside the rightmost palindrome (center c, right edge r), what is known about p[i]?

    By symmetry, the mirror index 2c - i has the same surroundings, as long as the palindrome stays within the big one.
  5. 5. Which problem is NOT solved directly by Manacher's algorithm?

    A subsequence may skip characters, which needs dynamic programming. Manacher handles contiguous substrings only.

Summary

  • A string of length n has 2n - 1 palindrome centers; every palindromic substring grows from one.
  • Brute force is O(nยณ), expand-around-center is O(nยฒ) with O(1) space.
  • Manacher inserts # separators, keeps the rightmost palindrome and copies radii from mirrored indexes, achieving O(n).
  • The longest palindrome starts at (i - p[i]) // 2 with length p[i]; the count is the sum of (p[i] + 1) // 2.
  • Subsequence and partitioning versions need dynamic programming.

Next: Suffix Arrays and Suffix Trees, which index every suffix of a string to answer many substring questions at once.