Palindromes

Problem

You are asked about palindromic substrings (contiguous pieces) of a string: the longest one, how many there are, or a way to cut the string into palindromes. Checking every substring by reversing it costs O(n) each, and there are O(n²) substrings, so O(n³) in all. Two observations cut that down: a palindrome is determined by its centre and radius, and a substring is a palindrome exactly when its ends match and the inside is a palindrome.

Intuition

Hold a palindrome up to a mirror at its middle: the left half matches the right half. So if you stand at the middle and step outward one letter on each side at a time, the palindrome keeps growing exactly as long as the two letters you touch are equal. The first mismatch ends it. A string of length n has n centres on letters (odd-length palindromes) and n - 1 centres between letters (even-length ones), so 2n - 1 places to try.

The other view is a table. Whether "abba" is a palindrome depends on its two end letters matching and on "bb" being a palindrome. "bb" in turn depends on its ends and the empty string in between. Every substring depends on a shorter one, so filling the table in order of length works.

Row is where the substring starts, column is where it ends. Green cells are palindromes, and the blue cell is the longest. The diagram scrolls sideways on a narrow screen.

Mechanics

Expand around centres

For each of the 2n - 1 centres, set two pointers: both on the same letter for an odd centre, or on neighbours for an even one. While both are in range and the letters match, record the palindrome, then move the left pointer one step left and the right one step right. When the loop stops, the last palindrome seen is the widest at that centre. The longest palindrome overall is the widest of these, and the count is the total number of successful steps.

The invariant: whenever the pointers are at (l, r) and the loop condition has just held, s[l..r] is a palindrome. It holds at the start (a single letter, or an empty gap that counts as a palindrome of length zero) and each step adds matching letters around a palindrome. The cost is O(n) per centre in the worst case, such as a string of one repeated letter, O(n²) in total, with O(1) extra space.

Each bar is the widest palindrome around that centre. The gap between the two b's grows from "bb" to the blue "abba".

The substring table

Define is_pal[i][j] as true when s[i..j] is a palindrome. Then is_pal[i][j] = (s[i] == s[j]) and (j - i < 2 or is_pal[i + 1][j - 1]). Spans of length 1 are always palindromes; spans of length 2 are palindromes when the two letters match; longer spans need their inner span to be one. Fill by increasing length (or with i descending), so the inner entry already exists. This costs O(n²) time and space, and it makes every later "is this piece a palindrome?" question O(1).

Manacher's algorithm

Put a separator between every pair of letters (and at both ends) so every palindrome has odd length in the padded string. Let radii[k] be how far the palindrome centred at k extends. Keep the centre and right edge of the palindrome that reaches furthest right. A new position k inside it has a mirror position on the other side, and the palindrome there already tells you a lower bound for k. Only positions that push the right edge further need new character comparisons, so the total work is O(n). For "cabbad" the padded string is #c#a#b#b#a#d# and the radii are 0, 1, 0, 1, 0, 1, 4, 1, 0, 1, 0, 1, 0; the largest radius, 4, is the length of "abba".

Invariant

The table is correct by induction on length: a string is a palindrome iff its first and last letters match and the part between them is a palindrome, and the part between is shorter. The expansion is correct because palindromes with the same centre are nested: if the radius-r palindrome exists, so does every smaller one, so the first mismatch rules out all larger.

Worked example

Take the string "cabbad". Expanding from the 11 centres finds the widest palindrome at each, as in the diagram, and the winner is "abba", starting at index 1. Counting every step that matched gives 8 palindromic substrings: 6 single letters, "bb" and "abba".

The table agrees: it has 8 true cells and the longest is "abba". The cell for "abba" (start 1, end 4) is true because a == a and the inner cell (start 2, end 3), "bb", is true. Manacher's radii give the same longest string, "abba", from the centre with radius 4.

Implementation

def longest_palindrome(s):
    best = ""
    for center in range(2 * len(s) - 1):
        left = center // 2
        right = left + center % 2
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        if right - left - 1 > len(best):
            best = s[left + 1:right]
    return best


def count_palindromes(s):
    count = 0
    for center in range(2 * len(s) - 1):
        left = center // 2
        right = left + center % 2
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

Variations and edge cases

def palindrome_table(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1])
    return is_pal


def min_cuts(s):
    is_pal = palindrome_table(s)
    cuts = list(range(-1, len(s)))        # cuts[i]: fewest cuts for s[:i]
    for end in range(1, len(s) + 1):
        for start in range(end):
            if is_pal[start][end - 1]:
                cuts[end] = min(cuts[end], cuts[start] + 1)
    return cuts[-1]


def manacher(s):
    t = "#" + "#".join(s) + "#"
    radii = [0] * len(t)
    center = right = 0
    for k in range(len(t)):
        if k < right:
            radii[k] = min(right - k, radii[2 * center - k])
        while (k - radii[k] - 1 >= 0 and k + radii[k] + 1 < len(t)
               and t[k - radii[k] - 1] == t[k + radii[k] + 1]):
            radii[k] += 1
        if k + radii[k] > right:
            center, right = k, k + radii[k]
    return radii

• Even centres. Forgetting the n - 1 gaps misses every even-length palindrome such as "abba". Starting both pointers at the same index only finds odd ones.
• Slicing the result. After the loop the pointers have stepped one past the palindrome, so the slice is s[left + 1:right].
• Table order. Iterating i ascending reads is_pal[i + 1][j - 1] before it is written. Go down in i or up in length.
• Empty and one-letter strings. The empty string has no centres; a single letter is its own answer. Return an empty string explicitly if needed.
• Case and punctuation. Questions about phrases clean the text first, then use two pointers; that is the two-pointers page, not this one.

Complexity and tradeoffs

• Time: centre expansion is O(n²) worst case and usually much faster on real text. The table is always O(n²). Manacher is O(n).
• Space: O(1) for expansion, O(n²) for the table, O(n) for Manacher.
• Baseline. Reversing every substring is O(n³).
• Which to use. For one question about the longest or the count, expansion is the shortest correct code. Use the table when later steps need constant-time palindrome checks, as in minimum cuts or partitioning. Manacher is the answer to "can you do it in linear time", and rarely required.
• When it fails. Subsequence questions (letters need not be adjacent) use a different table, over two ends of the string, on the string DP page. Palindromes under edits are an edit-distance variant.

Problems

Longest Palindromic Substring and Palindromic Substrings are the two textbook uses of centre expansion. Palindrome Partitioning and Palindrome Pairs use the same palindrome check inside a larger search.

Medium

• 5. Longest Palindromic Substring Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Every palindrome has a center, so expanding outward from each of the 2n-1 centers finds the longest one in quadratic time with constant space.
• 647. Palindromic Substrings Blind 75 NeetCode 150 NeetCode 250
  Expand around each of the 2n-1 centres and count every expansion that is still a palindrome.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 131. Palindrome Partitioning Medium
• 336. Palindrome Pairs Hard

Connections

Centre expansion is two pointers moving outward instead of inward. The table is a first example of DP over a pair of indices, which grid DP and two-string DP then generalise. Palindrome Partitioning combines the table with backtracking.

Check yourself

References

• Manacher, G. K., "A New Linear-Time On-Line Algorithm for Finding the Smallest Initial Palindrome of a String", Journal of the ACM 22(3), 1975.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14, the longest palindromic subsequence exercise.
• Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, section 9.2 (finding palindromes).
• Sedgewick and Wayne, Algorithms, section 5.3 (substring search): linear-time scanning that, like Manacher's algorithm, reuses earlier comparisons instead of restarting.
• Skiena, The Algorithm Design Manual, chapter 10 (dynamic programming).
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.