Palindromes

The brute force for the longest palindromic substring checks every substring and verifies each one: roughly n²/2 substrings times O(n) to compare characters, so O(n³). At n = 1,000 that is 5 × 10⁸ character comparisons, several seconds.

The waste is specific and worth naming before reaching for a fix. Verifying s[i..j] walks it from both ends, even though s[i+1..j-1] — the same string with one character shaved off each side — was verified moments ago. There are two ways to stop throwing that away: grow outward from the middle so the inner answer is already in hand, or write it down in a table.

Grow from the centre

Every palindrome has a centre. For an odd length the centre is a character; for an even length it is the gap between two characters. That gives n centres of the first kind and n-1 of the second: 2n - 1 centres in total, and every palindrome in the string sits at exactly one of them.

Expanding from an odd centre and an even centre of "abaab": the character centre grows to aba, the gap centre grows to baab100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

def longest_palindrome(s):
    if not s:
        return ''
    best = (0, 0)                      # (start, length)

    def expand(lo, hi):
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        return lo + 1, hi - lo - 1     # start, length

    for c in range(len(s)):
        for start, length in (expand(c, c), expand(c, c + 1)):
            if length > best[1]:
                best = (start, length)
    return s[best[0]:best[0] + best[1]]

The even centres are the ones people forget. A loop that only calls expand(c, c) looks complete, passes "babad", and is wrong: on "cbbd" it returns "c" instead of "bb", and on "abba" it returns "a". If a palindrome solution is failing and the expected answer has even length, this is the bug. The expand(c, c + 1) call is the whole fix — it starts with a zero-length window between two characters and grows from there.

Cost: 2n - 1 centres, each expansion running at most n/2 steps, so O(n²) time and O(1) extra space — two integers and a best-so-far. That product is only an upper bound; the reachable worst case is n²/2, because the successful steps across all centres count each palindromic substring exactly once and there are at most n(n+1)/2 of those. At n = 1,000 that is 5 × 10⁵ character comparisons, which is instant. At n = 10⁵ it is 5 × 10⁹, about 50 seconds at 10⁸ operations per second, which is the boundary the constraint table draws between n² and n log n.

That worst case is not exotic. A string of identical characters — "a" * n — makes every expansion run to the boundary, so the n²/2 bound is reached exactly, not approached: "a" * 1000 costs 500,500 successful comparisons, and every other string of that length costs fewer.

The DP table costs the same time and far more memory

The other fix writes the inner answers down. Let dp[i][j] be True when s[i..j] is a palindrome:

def longest_palindrome_dp(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    best = (0, 1) if n else (0, 0)
    for i in range(n):
        dp[i][i] = True
    for length in range(2, n + 1):                 # fill by increasing length
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                best = (i, length)
    return s[best[0]:best[0] + best[1]]

The recurrence reads directly: the ends must match, and the inside must already be a palindrome. The fill order matters — dp[i][j] depends on dp[i+1][j-1], a shorter span, so shorter spans have to be computed first.

Same O(n²) time as expansion, and O(n²) space, which is where it loses. At n = 5,000 the table has 5,000² = 25,000,000 cells. As a Python list of lists of booleans that is about 8 bytes per pointer, 200 MB — over any normal memory limit. Packed into bytearrays it is 25 MB, still 25 MB more than the two integers expansion uses.

So expansion is the default. The table earns its memory in exactly one situation: when you need is s[i..j] a palindrome answered many times rather than once. Palindrome partitioning — cut the string into the fewest pieces that are all palindromes — is an O(n²) DP that queries the predicate O(n²) times. It was going to build the table anyway, so the table is not an extra cost there. If the question asks for a single substring, it is.

Counting palindromic substrings is the same loop

Every successful step of an expansion is one distinct palindromic substring — distinct by position, which is what these questions count. So the count is the number of successful steps:

def count_palindromes(s):
    n, total = len(s), 0
    for c in range(2 * n - 1):
        lo, hi = c // 2, c // 2 + c % 2
        while lo >= 0 and hi < n and s[lo] == s[hi]:
            total += 1
            lo -= 1
            hi += 1
    return total

The c // 2, c // 2 + c % 2 line enumerates all 2n - 1 centres in a single loop: even c gives a character centre, odd c gives a gap. On "aaa" it returns 6 — three single characters, two "aa", one "aaa" — and the loop runs 1 + 1 + 2 + 1 + 1 steps to get there. Writing the centres as one range instead of two calls is also the version that is hardest to get wrong under pressure, because there is no second loop to forget.

Manacher, and whether you need it

Manacher's algorithm computes the palindrome radius at every centre in O(n) total. The idea is the mirror: inside a palindrome you already know about, the radius at a position is at least the radius at its mirror position, clipped to that palindrome's right boundary — so most centres start from a known lower bound instead of from zero. The bookkeeping is amortised the same way KMP's failure function is: the right boundary only ever moves right, at most n times in total.

Be honest about when this matters. Expansion is O(n²), and n has to reach about 10⁵ before that is too slow. Below that, Manacher buys nothing and costs you the twenty minutes of index arithmetic that its interleaved-separator trick needs to handle even lengths. Knowing it exists, what it costs, and why it is linear is worth more than being able to write it, because being asked to write it from memory is rare.

In an interview

Say the centre count out loud before writing anything: "Every palindrome has a centre, there are 2n - 1 of them counting the gaps, and expanding each is O(n), so O(n²) time and O(1) space." That sentence contains the algorithm, its complexity, and the even-length case, and it takes ten seconds.

When the interviewer asks for better than O(n²), name Manacher and its idea in one line, then say what it would cost you to write and ask whether they want it. That reads as judgement rather than a gap. It also matches how you should be choosing a pattern — the precondition here is the input size, and at n = 1,000 the precondition for needing Manacher is not met.

The mistake that loses points: handling only odd centres. It is invisible in "racecar" and fatal in "abba", and an interviewer who has seen it before will hand you an even-length example on purpose.

Check yourself

n = 2,000 and you need the longest palindromic substring. Expansion or the DP table?

Expansion. Both are O(n²) = 4 × 10⁶ steps, well inside limits, but expansion uses O(1) space where the table needs 4 million cells. Same time, less memory, less code.

Your solution returns "c" for "cbbd". What is wrong, in one line?

Only odd-length centres are being expanded. Add the expand(c, c + 1) call, or enumerate all 2n - 1 centres with the c // 2 form.

How many palindromic substrings does "aaaa" contain, and what does that tell you about the worst case?

10: four of length 1, three of length 2, two of length 3, one of length 4 — n(n+1)/2. Every expansion runs to the boundary, so an all-equal string is the exact worst case for the O(n²) bound, not just a bad case.