Longest Palindromic Substring — Expand Around Center

Longest Palindromic Substring is a Medium 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.

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.

Intuition

The brute force tries every substring and checks whether it is a palindrome: O(n^2) substrings times O(n) palindrome check, giving O(n^3). Too slow for n = 1000.

The key idea: a palindrome is defined by its center. There are 2n - 1 possible centers because a palindrome can be centered on a character (odd length) or between two characters (even length). For each center, expand outward as long as the two ends match. Each expansion is O(n) in the worst case, and there are O(n) centers, so total time is O(n^2). The space is O(1) because we only track the best window’s start and end.

The DP variant uses an n x n table of “is s[i..j] a palindrome?” and is also O(n^2) time but O(n^2) space. Expand-around-center wins on space.

Explanation with 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.

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.

s =  b   a   b   a   d         (n = 5,  2n - 1 = 9 centers)

odd centers (on a char):
     ^   ^   ^   ^   ^
     0   1   2   3   4

even centers (between chars):
       ^   ^   ^   ^
      0-1 1-2 2-3 3-4

each center -> expand left/right while s[L]==s[R]

indices: 0  1  2  3  4
chars  : b  a  b  a  d

start L=R=1            a            len 1
step L=0, R=2          b a b        match  len 3
step L=-1              out of bounds, stop

best palindrome here = "bab"

Code

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]

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int[] a = expand(s, i, i);
            int[] b = expand(s, i, i + 1);
            if (a[1] - a[0] > end - start) { start = a[0]; end = a[1]; }
            if (b[1] - b[0] > end - start) { start = b[0]; end = b[1]; }
        }
        return s.substring(start, end + 1);
    }
    private int[] expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
        return new int[]{l + 1, r - 1};
    }
}

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int start = 0, end = 0;
        auto expand = [&](int l, int r) {
            while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
            return pair<int,int>{l + 1, r - 1};
        };
        for (int i = 0; i < (int)s.size(); i++) {
            auto [l1, r1] = expand(i, i);
            auto [l2, r2] = expand(i, i + 1);
            if (r1 - l1 > end - start) { start = l1; end = r1; }
            if (r2 - l2 > end - start) { start = l2; end = r2; }
        }
        return s.substr(start, end - start + 1);
    }
};

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; total time is still O(n^2).
• 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.

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.
• 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 O(n^2) time and O(1) space, and mention Manacher’s existence without claiming to write it on the spot.

Related Problems

• Palindromic Substrings, which counts every palindrome using the same expansion idea.
• Longest Palindromic Subsequence, which is a true dynamic programming problem.
• Palindrome Number.

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

Wrap up

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.