Lesson 15 — Expand Around Center

~20 minutes · Day 13 · strings · Python

Today's interview problem is Longest Palindromic Substring. It sounds like a search problem: somewhere inside the string is the longest piece that reads the same forward and backward. The tempting move is to inspect every substring. The interview move is to notice that every possible answer must grow from a center.

The invariant

Every palindrome has a center; there are 2n-1 centers, so expand outward from each.

A palindrome is symmetric: the left and right characters match as you walk inward. That symmetry gives you permission to walk the other direction. Pick a center, compare the two sides, and expand while they match.

Each expansion asks one question: do the characters one step farther out still match?

Longest Palindromic Substring: the slow way first

The brute force approach is O(n³): choose every substring in O(n²), then check whether each one is a palindrome in O(n). It works, but it keeps rediscovering the same symmetry from scratch.

The center approach asks a smaller question: if this index, or this gap between indices, is the middle, how far can the palindrome grow?

def longest_palindrome(s):
    best_l = best_r = 0
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):       # odd center, even center
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l > best_r - best_l:
                    best_l, best_r = l, r      # longest seen so far
                l -= 1                         # expand left
                r += 1                         # expand right
    return s[best_l:best_r + 1]

There are two center shapes. An odd-length palindrome has a real character in the middle, like racecar. An even-length palindrome has a gap in the middle, like abba. For a string of length n, that is n character centers plus n - 1 gap centers: 2n - 1 total.

The loop checks a character center for odd palindromes and the next gap for even palindromes.

Transfer: same center, new question

Palindromic Substrings: instead of returning the longest palindrome, count how many palindromic substrings exist.

Before opening the reveal: keep the same centers. What changes inside the expansion loop?

def count_substrings(s):
    count = 0
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1       # every valid expansion is one palindrome
                l -= 1
                r += 1
    return count

What the trade buys you

Aside from the returned substring, the space stays constant because the algorithm only carries two best indices and the current left/right pointers. The speed improves because each center expands directly until symmetry breaks.

Practice — answer before you scroll past

Your move (tonight)

Solve Longest Palindromic Substring in your Notion tracker using the cycle — predict → attempt → compare → encode:

1. Predict: say the brute force and the center invariant out loud before writing code.
2. Attempt: code the center expansion with odd and even centers.
3. Compare: watch the source below only after a real attempt.
4. Encode: write the invariant in your own words: every palindrome grows from a center.