Palindrome Expansion

The problem

Given a string, find the longest contiguous substring that reads the same forwards and backwards. The brute force tests every (l, r) pair for palindromicity. O(n³). Expand-around-centre runs in O(n²); Manacher's reduces it to O(n).

Two kinds of centre

Every palindrome has a single centre. For odd-length palindromes (aba, radar) the centre is the middle character. For even-length ones (abba, noon) the centre is the gap between two characters. The two cases need to be enumerated separately.

For a string of length n, there are n possible odd centres (one per character) and n − 1 possible even centres (one per adjacent pair). Total: 2n − 1 centres.

The expansion routine

def longest_palindrome(s):
    if not s: return ""

    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        # When the loop exits, s[l+1..r) is the largest palindrome around this centre.
        return s[l + 1 : r]

    best = ""
    for i in range(len(s)):
        odd  = expand(i, i)            # centred on character i
        even = expand(i, i + 1)        # centred between i and i+1
        if len(odd) > len(best):  best = odd
        if len(even) > len(best): best = even
    return best

The two expansions are the only difference between odd and even cases, one starts with both pointers at the same index, the other with adjacent indices. The expansion logic is identical.

A worked trace

For s = "babad":

i = 0:  odd("b") = "b"        even("ba") = ""
i = 1:  odd("aba") = "aba"    even("ab") = ""
i = 2:  odd("bab") = "bab"    even("ba") = ""
i = 3:  odd("a") = "a"        even("ad") = ""
i = 4:  odd("d") = "d"        (even out of bounds)

Tied between "aba" and "bab" at length 3; either is a valid answer. The implementation returns whichever it sees first.

Complexity, reasoned

Outer loop: O(n) centres. Each expansion is O(n) in the worst case (string of all the same character, every centre extends to both ends). So worst-case time is O(n²). Memory: O(1) extra (we slice once at the end; the slice itself is O(answer length)). On uniform inputs the worst case is realised; on most natural strings it's much closer to O(n).

Manacher's algorithm, the O(n) version

Manacher's reuses information from earlier expansions to avoid redundant work. The key observation: if we've already found a palindrome P centred at C with right boundary R, and we're now looking at a new centre i ≤ R, then by the symmetry of P, the palindrome centred at the mirror of i (call it i') tells us the minimum length of the palindrome at i. We only need to expand beyond that minimum.

def manacher(s):
    # Insert sentinels so even and odd cases unify.
    t = '^#' + '#'.join(s) + '#$'
    p = [0] * len(t)
    centre = right = 0
    for i in range(1, len(t) - 1):
        mirror = 2 * centre - i
        if i < right:
            p[i] = min(right - i, p[mirror])
        while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
            p[i] += 1
        if i + p[i] > right:
            centre = i
            right = i + p[i]
    # Find the maximum p[i] and the corresponding substring.
    max_len, max_centre = max((p[i], i) for i in range(len(p)))
    start = (max_centre - max_len) // 2
    return s[start : start + max_len]

The sentinels (^, $, #) eliminate the odd/even distinction by inserting separators between every character and around the boundaries. The p[] array stores the radius of the largest palindrome centred at each position in the transformed string. The amortised argument: each expansion either falls within the current right boundary (O(1) per centre) or extends it (each extension does at most n work across the whole run).

Total: O(n). The implementation is significantly more involved than expand-around-centre. For interview contexts, expand-around-centre is the expected answer; Manacher is the bonus.

The "count palindromic substrings" variant

Same machinery, different aggregation. Instead of returning the longest palindrome, count every successful expansion step, each one corresponds to a distinct palindromic substring.

def count_palindromes(s):
    def expand(l, r):
        count = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
        return count
    return sum(expand(i, i) + expand(i, i + 1) for i in range(len(s)))

O(n²) time, O(1) memory. Each successful character match contributes one palindrome to the count.

When O(n²) is fine and when it isn't

Up to n ≈ 10⁴, expand-around-centre runs in milliseconds, fine for any interview context. Beyond n ≈ 10⁵ on adversarial inputs (long strings of repeated characters), Manacher's is the correct choice. Production text-processing libraries usually implement Manacher; interview submissions usually don't need to.

Where beginners go wrong

• Forgetting the even case. Searching only odd centres misses palindromes like "abba". Both expansions per centre are required.
• Returning the wrong slice. When the expansion stops, l and r are one past the boundary on each side. The valid palindrome is s[l + 1 : r], not s[l : r + 1].
• Comparing palindromes by string equality instead of length. Tracking the longest with if odd > best compares lexicographically, not by length. Always compare lengths.
• Trying to use prefix-sum or hash techniques. Palindromes don't have a useful prefix structure for this problem; the centre-based approach is the right shape.

What to read next

The Strings module covers Manacher in the broader context of linear-time string algorithms. The Two Pointers module formalises the expand-around-centre pattern as one shape of converging-pointer technique.