LeetCode Longest Palindromic Substring: Expand Around Center

LeetCode 5, Longest Palindromic Substring, is a Medium problem and a frequent interview pick. The brute force is obvious and slow, the dynamic programming solution is reasonable but space heavy, and the expand-around-center technique threads the needle with O(n^2) time and O(1) extra space. We will look at all three so you can defend your choice in a real interview.

The Problem

Given a string s, return the longest palindromic substring in s. A substring is contiguous, unlike a subsequence.

Example 1:

• Input: s = "babad"
• Output: bab (note that aba is also valid)

Example 2:

• Input: s = "cbbd"
• Output: bb

Constraints typically allow s up to length 1000, which rules out cubic solutions.

Brute Force

Try every substring and check whether it is a palindrome.

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

There are O(n^2) substrings and each palindrome check is O(n), so this is O(n^3) time. With n = 1000 that is 10^9 operations and a guaranteed timeout.

Optimal Solution

A palindrome is defined by its center. There are 2n - 1 possible centers because a palindrome can be centered on a character for odd lengths or between two characters for even lengths. For each center, expand outward as long as the two ends match.

def longestPalindrome(s: str) -> str:
    if not s:
        return ""

    start, end = 0, 0

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

    for i in range(len(s)):
        l1, r1 = expand(i, i)
        l2, r2 = expand(i, i + 1)
        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2

    return s[start:end+1]

Each expand call runs in O(n) in the worst case, and we call it twice per index. That gives O(n^2) time and O(1) extra space, which is the best general-purpose answer most interviewers expect. Manacher’s algorithm reaches O(n), but it is rarely required and almost never written from memory.

Walk Through an Example

Take s = "babad". We iterate i from 0 to 4.

• i = 0: odd expand around b gives b. Even expand between b and a fails immediately.
• i = 1: odd expand around a extends to bab because s[0] = b matches s[2] = b. Best so far is bab.
• i = 2: odd expand around b extends to aba. It ties the current best in length, so we keep bab because we updated only on strict improvement.
• i = 3: odd expand around a gives a. Even expand between a and d fails.
• i = 4: odd expand around d gives d.

We return bab. Either bab or aba is accepted by the grader.

Now s = "cbbd". The interesting step is i = 1: the even expand between s[1] = b and s[2] = b succeeds, giving bb. No later expand beats length 2, so the answer is bb.

Edge Cases

• Empty string: return the empty string directly. The loop body never runs.
• Single character: every single character is a palindrome of length 1.
• All identical characters like aaaa: every center expands to the full string. Time is still O(n^2) because each expansion is short or long depending on position, summing to a quadratic total.
• Two characters: the even expand catches aa. If they differ, the best length is 1.
• Unicode: the algorithm works on any iterable of comparable units. Be careful if you iterate over bytes versus code points.

Complexity Analysis

• Brute force: O(n^3) time, O(1) extra space.
• Dynamic programming with a 2D table: O(n^2) time, O(n^2) space.
• Expand around center: O(n^2) time, O(1) extra space.
• Manacher’s algorithm: O(n) time, O(n) extra space. Powerful but rarely necessary.

If the complexity notation is fuzzy, our refresher on Big O notation is worth a quick read.

How to Explain It in an Interview

• Define what counts as a palindrome and note that it must be contiguous.
• Mention the cubic baseline, then dismiss it on the stated constraints.
• Introduce the idea that every palindrome has a center, and that there are 2n - 1 possible centers.
• Describe the two-pointer expansion clearly: start from the center, push outward while characters match.
• Conclude with the O(n^2) time and O(1) space, and mention Manacher’s existence without claiming to write it on the spot.

This framing shows that you reach for structure rather than memorization.

Related Problems

• LeetCode 647, Palindromic Substrings, which counts every palindrome using the same expansion idea.
• LeetCode 516, Longest Palindromic Subsequence, which is a true dynamic programming problem.
• LeetCode 9, Palindrome Number, which is a warmup using digit math.

For more on processing characters and substrings, see strings introduction and operations and pattern matching basics.

Wrap up

Longest Palindromic Substring is the canonical test of the expand-around-center technique. Once you internalize that every palindrome is anchored by a center and that there are only 2n - 1 of them, the O(n^2) solution falls out naturally. Practice the two-loop variant until the odd and even cases feel symmetric, and you will breeze through this question and its siblings.