Expand Around Center

Expand Around Center

LeetCode 5. Longest Palindromic Substring asks for the longest palindromic substring of a given string. Every palindrome has a center. For odd-length palindromes like "racecar" the center is a single character, the middle 'e'. For even-length palindromes like "abba" the center sits between two characters, between the two 'b's. This observation is the seed of the expand-around-center technique: instead of asking "is this substring a palindrome?", ask "what is the longest palindrome centered here?" and expand outward to find the answer.

The $2n-1$ Centers Insight

A string of length $n$ has exactly $2n-1$ possible centers: $n$ centers for odd-length palindromes (one per character) and $n-1$ centers for even-length palindromes (one per adjacent pair). Visiting each center and expanding takes $O(n)$ per center in the worst case, giving an overall time complexity of $O(n²)$ with $O(1)$ extra space, far better than the $O(n²)$ space required by a full DP table.

The Expansion Process

For a given center, you maintain two pointers l and r that start at the center and walk outward as long as the characters they point to match. When s[l] != s[r] (or a pointer walks off the string), the palindrome bounded by [l+1, r-1] is the longest one at that center.

def expand(s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    # After the loop, s[l+1:r] is the palindrome
    return l + 1, r - 1

For odd-length palindromes, start with l = r = i. For even-length palindromes, start with l = i and r = i + 1. Both cases are handled in a single pass over the string.

Walked Example: Longest Palindromic Substring in "babad"

Consider s = "babad". We iterate over each center:

• Center i=0, odd: expand from "b": only "b" itself, length 1.
• Center i=0/1, even: s[0]='b', s[1]='a' don't match; length 0.
• Center i=1, odd: expand from "a": s[0]='b' vs s[2]='b', match! Expand again: l goes to -1, stop. Palindrome is "bab", length 3.
• Center i=1/2, even: s[1]='a', s[2]='b' don't match; length 0.
• Center i=2, odd: expand from "b": s[1]='a' vs s[3]='a', match! Expand again: l goes to 0, s[0]='b' vs s[4]='d', no match. Palindrome is "aba", length 3.
• Center i=3, odd: expand from "a": s[2]='b' vs s[4]='d', no match. Just "a".
• Center i=4, odd: "d" alone.

Both "bab" and "aba" are length 3. The algorithm returns the first one found, which is "bab".

Full Implementation

def longest_palindrome(s: str) -> str:
    res = ""
    for i in range(len(s)):
        for l, r in [(i, i), (i, i + 1)]:
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            # s[l+1:r] is the palindrome found at this center
            if r - l - 1 > len(res):
                res = s[l + 1 : r]
    return res

The inner loop handles both center types in one elegant structure. After the while loop exits, l has overshot one step left and r one step right, so the actual palindrome is s[l+1:r] and its length is r - l - 1.

Variant: Counting Palindromic Substrings

LeetCode 647. Palindromic Substrings asks for the total number of palindromic substrings.

To count every palindromic substring rather than find the longest, change the bookkeeping: increment a counter on each successful expansion step rather than tracking the maximum length.

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

Each iteration of the while body corresponds to one valid palindrome being discovered at that center, so incrementing inside the loop naturally counts all of them, including single characters (the first iteration of the odd-center loop always succeeds when l == r).

Connection to Manacher's Algorithm

The expand-around-center approach is $O(n²)$ because it may redo work: if a long palindrome was found at center i, the palindromes centered inside it could be determined from symmetry rather than re-expanded. Manacher's algorithm exploits exactly this observation by maintaining a "rightmost boundary" palindrome and using previously computed radii to initialize new expansions, reducing the total work to $O(n)$. For most LeetCode problems, the $O(n²)$ approach is perfectly sufficient. Manacher's is worth knowing exists but rarely needed in interviews.

Complexity

• Time: $O(n²)$: up to $2n-1$ centers, each expanding up to $O(n)$ steps.
• Space: $O(1)$ extra, not counting the output string.

Recognizing this pattern

You're probably looking at expand-around-center when:

• The problem mentions palindromic substrings: longest, count of, or all of them.
• $n \le$ a few thousand, so $O(n^2)$ comfortably fits the budget and Manacher's isn't required.
• You need both odd and even palindromes, and the easiest framing is "try every center."
• The output is the palindrome itself (start/end indices), not just a derived count where DP would also work.

Common templates:

• Longest palindromic substring: track best (i, length) while expanding from each of the $2n-1$ centers. Example: Longest Palindromic Substring.
• Count all palindromic substrings: increment counter inside the expansion while loop. Example: Palindromic Substrings.
• Palindrome with one allowed deletion: branch the expansion when characters mismatch and recurse on both shortened windows. Example: Valid Palindrome II.
• Longest palindrome by reordering characters: count parities; one center plus pairs. Example: Longest Palindrome.