Longest Palindromic Substring: Expand Around Center in O(n²)

The longest palindromic substring has a linear-time algorithm, but it is long, subtle, and easy to get wrong under pressure. The answer worth knowing cold is simpler: expand around every centre. It is O(n²), needs no table, and fits in a dozen lines — provided you remember that half the centres are not characters at all.

The problem it solves

Given a string, return its longest substring that reads the same forwards and backwards. For babad that is bab (or aba, which is just as long). For cbbd it is bb.

A substring is contiguous, which is what separates this from the longest palindromic subsequence, a different problem with a dynamic-programming answer.

Brute force checks every substring — there are about n² / 2 of them — and spends up to O(n) on each palindrome check, for O(n³) total. A DP table can bring that to O(n²) time, but it also takes O(n²) memory to record which substrings are palindromes.

The intuition

Turn the question around. Instead of asking "is this substring a palindrome?" for every substring, ask "how far does the palindrome around this point extend?" for every point.

A palindrome is symmetric about its middle. If you know the middle, you can find the longest palindrome there by pushing two pointers outwards — one left, one right — for as long as the characters under them match. The moment they differ, or a pointer runs off the end, the palindrome around that middle is as long as it will get.

The catch is what counts as a middle:

• An odd-length palindrome like aba is centred on a character.
• An even-length palindrome like abba is centred on the gap between two characters.

A string of length n has n characters and n - 1 gaps, so 2n - 1 centres. Try each one, keep the longest result, and you have examined every palindrome's middle — so you cannot have missed the longest.

Watch it run

The animation walks the centres of babad. The first b stops at length 1 because there is nothing to its left. The a at index 1 grows to bab. The second b grows to aba, which ties but does not replace the best. Then a gap centre between a and b fails on its very first comparison — even centres die quickly unless two equal letters sit side by side.

The code

One loop over all 2n - 1 centres. Integer division maps a centre number to its starting pointers: even numbers are characters, odd numbers are gaps. A second function counts comparisons on two very different inputs:

def longest_palindrome(s):
    best_lo, best_hi = 0, 0                     # s[best_lo:best_hi] is the answer
    for centre in range(2 * len(s) - 1):        # n letters + (n - 1) gaps
        lo = centre // 2
        hi = lo + centre % 2                    # a letter: lo == hi; a gap: hi == lo + 1
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        if hi - lo - 1 > best_hi - best_lo:     # the loop overshot by one each side
            best_lo, best_hi = lo + 1, hi
    return s[best_lo:best_hi]

def count_compares(s):                          # the same loop, counting s[lo] == s[hi]
    total = 0
    for centre in range(2 * len(s) - 1):
        lo, hi = centre // 2, centre // 2 + centre % 2
        while lo >= 0 and hi < len(s):
            total += 1
            if s[lo] != s[hi]:
                break
            lo, hi = lo - 1, hi + 1
    return total

print(longest_palindrome("babad"))              # bab
print(longest_palindrome("cbbd"))               # bb
print(longest_palindrome("forgeeksskeegfor"))   # geeksskeeg
print(count_compares("abcdefghij" * 100), count_compares("a" * 1000))   # 2997 500500

The two counts show the gap between the typical case and the worst case. On 1,000 characters with no repeated neighbours, every centre dies after a comparison or two: 2,997 in total. On 1,000 copies of one letter, every centre expands to an edge: 500,500 comparisons, which is n(n + 1) / 2.

The check compares against the definition with nothing clever in it — try every length from the longest down, and every start, and return the first palindrome found. A two-letter alphabet makes long palindromes common, which is where an off-by-one in the pointer arithmetic would show:

import random

def longest_brute(s):                           # every substring, longest first
    for length in range(len(s), 0, -1):
        for start in range(len(s) - length + 1):
            piece = s[start:start + length]
            if piece == piece[::-1]:
                return length
    return 0

random.seed(4)
ok = True
for _ in range(4000):
    s = "".join(random.choice("ab") for _ in range(random.randint(0, 14)))
    got = longest_palindrome(s)
    ok &= got == got[::-1] and got in s and len(got) == longest_brute(s)
print(ok)                                       # True

It checks three things about each answer: it is a palindrome, it really occurs in the input, and nothing longer exists. Lengths start at 0, so the empty string is covered too.

The complexity

There are 2n - 1 centres, and each expansion makes at most about n / 2 steps before a pointer leaves the string, so O(n²) time in the worst case — the all-same-letter count above is exactly that. Memory is two pairs of indices: O(1). The answer is sliced once at the end rather than on every improvement, which keeps the loop free of copying.

Manacher's algorithm reaches O(n) by reusing the mirror image of palindromes already found. It is worth knowing it exists; it is also far longer to write and to explain.

Where it goes wrong

• Only odd centres. Looping over characters alone finds aba but never abba. On cbbd it returns a single letter instead of bb.
• The overshoot. The loop exits one step past the palindrome on both sides. The real palindrome is s[lo + 1:hi], of length hi - lo - 1, not hi - lo + 1.
• Slicing on every improvement. Storing s[lo + 1:hi] each time the best grows copies characters inside the loop. Keep indices; slice once.
• Confusing substring and subsequence. If characters may be skipped, the problem is the subsequence one, and expansion does not apply.

For the two-pointer check this builds on, see valid palindrome.

How to say it in an interview

"Every palindrome is symmetric about a centre, and there are 2n - 1 possible centres: each character for odd lengths, each gap for even lengths. From each centre I expand two pointers while the characters match, and track the longest span. That's O(n²) time and O(1) space, with no table. Manacher's algorithm gets O(n), but expand-around-centre is the one I'd write here."

Mentioning the even centres before you are asked about abba is the detail that shows you have actually worked the problem.