Longest Palindromic Substring: Expand Around Center

Key Insights

• Every palindrome has a center, and expanding outward from each potential center gives us an O(n²) solution with O(1) space—a significant improvement over brute force O(n³).
• A string of length n has 2n-1 potential centers: n character positions for odd-length palindromes and n-1 gaps between characters for even-length palindromes.
• The expand-around-center technique is the sweet spot for interviews and production code—it’s intuitive, efficient, and requires no auxiliary data structures.

Introduction & Problem Statement

The longest palindromic substring problem asks you to find the longest contiguous sequence of characters within a string that reads the same forwards and backwards. Given “babad”, valid answers include “bab” or “aba”. Given “cbbd”, the answer is “bb”.

This isn’t just an academic exercise. Palindrome detection appears in DNA sequence analysis where scientists look for palindromic sequences that indicate potential hairpin structures. Text processing applications use it for pattern matching and data validation. And of course, it’s a staple in technical interviews because it tests your ability to recognize patterns and optimize beyond the obvious solution.

A substring is palindromic when it mirrors itself around its center. “racecar” reads the same from both ends. “noon” does too. The naive approach—checking every possible substring—works but wastes enormous computational resources. We can do better by thinking about what makes palindromes special.

Why “Expand Around Center”?

The brute force approach generates all O(n²) substrings and checks each one for palindromicity in O(n) time, yielding O(n³) total complexity. For a 10,000-character string, that’s a trillion operations. Unacceptable.

The key insight is geometric: every palindrome is symmetric around its center. Instead of checking arbitrary substrings, we can place ourselves at each potential center and expand outward, comparing characters as we go. The moment characters don’t match, we stop—no palindrome can extend further from that center.

This flips the problem. Rather than validating substrings, we’re growing palindromes from their cores. Each expansion operation is O(n) in the worst case (imagine “aaaa…”), and we have O(n) centers to check, giving us O(n²) time. But we only need a few variables to track our best result—O(1) space.

The improvement from O(n³) to O(n²) matters. That 10,000-character string now requires only 100 million operations. Still not instant, but tractable.

Understanding Palindrome Centers

Here’s where many developers stumble: palindromes come in two flavors, and they have different center structures.

Odd-length palindromes like “aba” center on a single character—the ‘b’. Even-length palindromes like “abba” center on the gap between the two ‘b’s. There’s no single character at the center.

For a string of length n, we have:

• n characters that can serve as centers for odd-length palindromes
• n-1 gaps between adjacent characters for even-length palindromes

That’s 2n-1 potential centers total. For “abba” (length 4), we check 7 centers: positions 0, 0.5, 1, 1.5, 2, 2.5, and 3 (where decimals represent gaps).

In practice, we handle this by writing an expansion function that takes two indices—left and right. For odd-length checks, we start with left == right. For even-length checks, we start with right == left + 1.

def expand_from_center(s: str, left: int, right: int) -> tuple[int, int]:
    """
    Expand outward from the given center position.
    Returns the start and end indices of the longest palindrome found.
    """
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    
    # When the loop exits, left and right have gone one step too far
    # The valid palindrome is from left+1 to right-1 (inclusive)
    return left + 1, right - 1

This function handles both cases elegantly. When left == right, we’re checking an odd-length palindrome centered on a single character. When right == left + 1, we’re checking an even-length palindrome centered on the gap between two characters.

Algorithm Implementation

Now let’s build the complete solution. We iterate through each character position, try both odd and even expansions, and track the longest palindrome we’ve found.

def longest_palindrome(s: str) -> str:
    """
    Find the longest palindromic substring using expand-around-center.
    Time: O(n²), Space: O(1)
    """
    if not s:
        return ""
    
    start, end = 0, 0  # Track best palindrome bounds
    
    for i in range(len(s)):
        # Try odd-length palindrome centered at i
        left1, right1 = expand_from_center(s, i, i)
        
        # Try even-length palindrome centered between i and i+1
        left2, right2 = expand_from_center(s, i, i + 1)
        
        # Update best if we found a longer palindrome
        if right1 - left1 > end - start:
            start, end = left1, right1
        if right2 - left2 > end - start:
            start, end = left2, right2
    
    return s[start:end + 1]


def expand_from_center(s: str, left: int, right: int) -> tuple[int, int]:
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return left + 1, right - 1

Here’s the same logic in JavaScript for those working in that ecosystem:

function longestPalindrome(s) {
    if (!s || s.length === 0) return "";
    
    let start = 0, end = 0;
    
    for (let i = 0; i < s.length; i++) {
        // Odd-length expansion
        const [left1, right1] = expandFromCenter(s, i, i);
        // Even-length expansion
        const [left2, right2] = expandFromCenter(s, i, i + 1);
        
        if (right1 - left1 > end - start) {
            start = left1;
            end = right1;
        }
        if (right2 - left2 > end - start) {
            start = left2;
            end = right2;
        }
    }
    
    return s.substring(start, end + 1);
}

function expandFromCenter(s, left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    return [left + 1, right - 1];
}

Dry Run with Examples

Let’s trace through “babad” step by step:

Best found: “bab” (length 3). Note that “aba” ties but doesn’t replace.

Now “cbbd”:

Best found: “bb” (length 2). The even-length expansion at position 1 catches it.

Edge Cases & Optimizations

Production code needs to handle the weird inputs:

• Empty string: Return empty immediately
• Single character: It’s a palindrome of length 1
• All identical characters: “aaaa” should return “aaaa”—the whole string
• No palindrome longer than 1: “abcd” returns any single character

We can also add an early termination optimization. If the remaining characters can’t possibly beat our current best, stop early:

def longest_palindrome_optimized(s: str) -> str:
    if not s:
        return ""
    if len(s) == 1:
        return s
    
    start, end = 0, 0
    
    for i in range(len(s)):
        # Early termination: if remaining length can't beat current best, stop
        remaining = len(s) - i
        current_best = end - start + 1
        if remaining * 2 - 1 <= current_best:
            break
        
        # Odd-length expansion
        left1, right1 = expand_from_center(s, i, i)
        if right1 - left1 > end - start:
            start, end = left1, right1
        
        # Even-length expansion
        left2, right2 = expand_from_center(s, i, i + 1)
        if right2 - left2 > end - start:
            start, end = left2, right2
    
    return s[start:end + 1]

The early exit condition remaining * 2 - 1 <= current_best works because the maximum possible palindrome starting at position i has length at most 2 * remaining - 1 (if it extends to the end and mirrors back).

Complexity Analysis & Comparison

Time Complexity: O(n²)

We iterate through n centers. Each expansion can visit at most n characters (in the worst case of a string like “aaaaa”). Therefore: O(n) centers × O(n) expansion = O(n²).

Space Complexity: O(1)

We use only a fixed number of variables regardless of input size. The returned substring doesn’t count toward auxiliary space.

Comparison to Manacher’s Algorithm

Manacher’s algorithm achieves O(n) time by cleverly reusing information from previously computed palindromes. It transforms the string to handle odd/even cases uniformly and maintains an array of palindrome radii. While theoretically superior, it’s significantly more complex to implement correctly and harder to debug.

For most practical applications, the expand-around-center approach is the right choice. It’s fast enough for strings up to tens of thousands of characters, easy to understand, and trivial to verify. Save Manacher’s for competitive programming or when you’re processing millions of strings where that constant factor matters.

The expand-around-center technique exemplifies a broader principle: sometimes the best algorithm isn’t the asymptotically optimal one, but the one that’s correct, maintainable, and fast enough.