Longest Palindromic Substring: Expand From Center

LeetCode 5, Longest Palindromic Substring, is one of those problems that feels like it should be harder than it actually is. You are given a string s and need to return the longest substring that reads the same forward and backward. The trick is that a brute force check of every possible substring is O(n^3), but the expand from center technique brings it down to O(n^2) with a really clean implementation.

Let's break it down.

The problem

Given a string s, return the longest palindromic substring in s.

A few examples:

• "babad" returns "bab" (or "aba", both are valid).
• "cbbd" returns "bb".
• "a" returns "a".

The constraints say the string can be up to 1000 characters long, so O(n^2) is perfectly fine.

Brute force: check every substring

The most obvious approach is to generate every possible substring, check if it is a palindrome, and track the longest one.

def longest_palindrome_brute(s):
    best = ""
    for i in range(len(s)):
        for j in range(i, len(s)):
            sub = s[i:j + 1]
            if sub == sub[::-1] and len(sub) > len(best):
                best = sub
    return best

This works, but it is O(n^3): O(n^2) substrings, each taking O(n) to verify. For n = 1000, that is a billion operations. Too slow.

The key insight: every palindrome has a center

Here is the idea that makes the expand from center technique work. Every palindrome is symmetric around its center. Instead of checking all substrings, you can pick each possible center and expand outward as long as the characters on both sides match.

For a string of length n, there are 2n - 1 possible centers:

• n odd-length centers: each character can be the center of an odd-length palindrome like "aba".
• n - 1 even-length centers: each pair of adjacent characters can be the center of an even-length palindrome like "abba".

This distinction between odd and even length palindromes is critical. If you only check odd-length centers, you will miss palindromes like "bb" or "abba". If you only check even-length centers, you will miss single characters and odd-length ones like "aba".

Odd vs even length palindromes

An odd-length palindrome has a single center character. For "racecar", the center is e at index 3. You expand outward: s[2] == s[4] (c == c), s[1] == s[5] (a == a), s[0] == s[6] (r == r).

An even-length palindrome has its center between two characters. For "abba", the center is between the two bs. You start by comparing s[1] and s[2] (b == b), then expand: s[0] and s[3] (a == a).

In the code, the difference is just the starting positions of the two pointers:

• Odd: left = center, right = center
• Even: left = center, right = center + 1

The expand from center solution

def longest_palindrome(s):
    best_start = 0
    best_len = 1

    def expand(left, right):
        nonlocal best_start, best_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # After the loop, left and right are one step past the palindrome
        length = right - left - 1
        if length > best_len:
            best_start = left + 1
            best_len = length

    for i in range(len(s)):
        expand(i, i)      # odd-length palindromes
        expand(i, i + 1)  # even-length palindromes

    return s[best_start:best_start + best_len]

That is the whole thing. The expand helper does the heavy lifting. It takes two pointers and pushes them outward as long as the characters match. When it stops, we calculate the length of the palindrome found and update the best if it is longer.

Visual walkthrough

Let's trace the algorithm on "babad". We check each center (showing only the interesting odd-length expansions here for clarity).

Notice how center 1 finds "bab" and center 2 finds "aba". Both are length 3. Since "bab" is found first, it stays as the answer. Either would be accepted by the judge.

Why expand from center works

Think about it this way. If you are standing in the middle of a palindrome, the characters to your left and right are mirror images. The moment you find a mismatch, you know the palindrome cannot extend any further from that center. So you move on to the next center.

The reason this is O(n^2) and not O(n^3) is that each expansion does useful work. When you expand from center i and find a palindrome of length k, you did k/2 comparisons. Across all 2n - 1 centers, the total number of comparisons is bounded by O(n^2) because each expansion is limited by the string boundaries.

Complexity analysis

Time: O(n^2). There are 2n - 1 centers. In the worst case (like "aaaa...a"), each expansion takes O(n) time. Total: O(n * n) = O(n^2).

Space: O(1). We only track the start index and length of the best palindrome. No auxiliary data structures.

For interview purposes, expand from center hits the sweet spot: optimal enough to pass and simple enough to code under pressure.

The building blocks

Longest Palindromic Substring is built from one fundamental brick that shows up in many two pointer and string problems.

Opposite-end convergence

The expand helper is a form of opposite-end convergence, but in reverse. Instead of two pointers starting at the edges and moving inward (like in Valid Palindrome), here the two pointers start at the center and move outward. The comparison logic is the same: check if the values at both pointers match, then move both pointers one step further apart.

The shape is:

1. Initialize left and right at or near the center.
2. While both pointers are in bounds and s[left] == s[right], expand outward.
3. When a mismatch occurs (or you hit the boundary), stop and record the palindrome length.

This "expand outward" variation of opposite-end convergence is the same technique used in Palindromic Substrings (LeetCode 647), where you count all palindromic substrings instead of finding the longest one. If you can write the expand helper from scratch, you can solve both problems.

Other problems that use opposite-end convergence:

• Valid Palindrome (inward convergence to verify)
• Palindromic Substrings (outward expansion to count)
• Container With Most Water (inward convergence on heights)
• 3Sum (inner loop with converging pointers)

Common mistakes

Forgetting even-length palindromes. If you only call expand(i, i), you will miss palindromes like "bb" and "abba". Always call both expand(i, i) and expand(i, i + 1).

Off-by-one in the length calculation. After the while loop, left and right have already moved past the valid palindrome. The palindrome runs from left + 1 to right - 1, so its length is right - left - 1, not right - left + 1.

Returning the length instead of the substring. The problem asks for the actual substring, not its length. Make sure to track the start index and slice the string at the end.

Not handling single-character strings. A single character is always a palindrome. Initialize best_len = 1 to handle this naturally.

Edge cases worth knowing

All identical characters. "aaaa" has its longest palindrome as the entire string. The first center expansion will catch most of it, and subsequent centers will not beat it.

No palindrome longer than 1. "abcd" returns any single character (say "a"). Every single character is a palindrome by definition.

Even-length result. "cbbd" returns "bb". This is found by the expand(i, i + 1) call when i = 1.

Reading about it is not enough

The expand from center technique is one of those things that looks trivial on paper. You read the solution, nod, and think you have it. But try writing it from scratch two weeks from now. The expand helper, the odd vs even distinction, the length calculation with right - left - 1, the tracking of best_start vs best_len. These details are exactly what slip away.

The opposite-end convergence building block is small. It takes a few minutes to drill. But once it is burned into your long-term memory, you can assemble the full solution for this problem and related palindrome problems without hesitation.

Related posts

• Palindromic Substrings - Uses the same expand from center technique to count all palindromic substrings
• Valid Palindrome - The simpler inward-convergence version of the same pattern
• The Two Pointers Pattern - The foundational pattern behind opposite-end convergence