LeetCode #5 — Medium

Longest Palindromic
Substring

A complete visual walkthrough of the expand-around-center approach — from brute force to elegant O(n²) solution.

The Problem

Problem Statement

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

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

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Step 01

Brute Force — Check Every Substring

The naive approach: enumerate every possible substring, check if it is a palindrome, and track the longest one found.

Checking substrings of "babad"

For a string of length n, there are n(n+1)/2 substrings. Each palindrome check takes O(n) time, giving O(n³) total.

len=5

not palindrome

len=4

not palindrome

len=3

palindrome! "bab"

We must check every substring at every starting position — even after finding "bab", we continue checking the rest. This is wasteful.

💡

O(n³) is too slow. For n = 1000, that is up to 1 billion operations. We need an approach that avoids redundant checking. What if we could grow palindromes outward from their centers instead?

Step 02

The Core Insight — Expand Around Center

Every palindrome has a center. For odd-length palindromes, the center is a single character. For even-length palindromes, the center is the gap between two characters.

Two Types of Centers

ODD LENGTH

Center = single char "c"

expand(s, i, i)

EVEN LENGTH

Center = two chars "bb"

expand(s, i, i+1)

For a string of length n, there are 2n - 1 possible centers (n single-character centers + n-1 between-character centers). From each center, we expand outward while characters match.

⚡

The key advantage: expansion stops the moment characters do not match. We never check substrings that cannot possibly be palindromes. Each expansion takes at most O(n), and there are O(n) centers, giving us O(n²) total — a huge improvement over brute force.

Step 03

Algorithm Walkthrough

Let's trace through "babad" step by step, expanding from each center.

Center i = 0: "b" (odd expansion)

Cannot expand left (at boundary). Palindrome: "b" (length 1)

Center i = 1: "a" (odd expansion)

← expand →

s[0]='b' == s[2]='b'? Yes! Expand further: s[-1] is out of bounds. Stop.

Palindrome: "bab" (length 3) — new best!

Center i = 2: "b" (odd expansion)

← expand →

s[1]='a' == s[3]='a'? Yes! Expand: s[0]='b' == s[4]='d'? No! Stop.

Palindrome: "aba" (length 3) — ties the best.

Even-length check: centers (0,1), (1,2), (2,3), (3,4)

(0,1) s[0]='b' != s[1]='a' len=0

(1,2) s[1]='a' != s[2]='b' len=0

(2,3) s[2]='b' != s[3]='a' len=0

(3,4) s[3]='a' != s[4]='d' len=0

No adjacent duplicates in "babad", so no even-length palindromes longer than 0.

🎯

Result: "bab" (or "aba") — both are length 3 palindromes found by expanding from centers at index 1 and 2 respectively. The algorithm returns whichever it finds first.

Even-length example: "cbbd"

← expand from center (1,2) →

s[1]='b' == s[2]='b'? Yes! Expand: s[0]='c' == s[3]='d'? No! Stop. Palindrome: "bb" (length 2)

Step 04

Edge Cases

The expand-around-center approach handles all edge cases naturally, without special-case code.

Cases to Consider

"a" → "a" Single character is always a palindrome.
"aaaa" → "aaaa" All same characters. Expansion from center i=1 (even) or i=2 (odd) covers the full string.
"racecar" → "racecar" Entire string is a palindrome. Expanding from center i=3 finds it.
"abcde" → "a" No palindrome longer than 1. Every character is its own palindrome.
"" → "" Empty or null string. The guard clause handles this immediately.

💡

No special-case code needed. The loop naturally handles single characters (expansion returns 1), all-same characters (expansion reaches boundaries), and no-palindrome cases (each center yields length 1). The only guard is for null/empty input.

Step 05

Full Annotated Code

class Solution {
    public String longestPalindrome(String s) {

        // Guard: handle null or empty input
        if (s == null || s.length() < 1) return "";

        int start = 0, maxLen = 0;

        // Try every possible center
        for (int i = 0; i < s.length(); i++) {

            // Odd-length palindrome: single char center
            int len1 = expand(s, i, i);

            // Even-length palindrome: two char center
            int len2 = expand(s, i, i + 1);

            // Take the longer of the two expansions
            int len = Math.max(len1, len2);

            // Update best if this palindrome is longer
            if (len > maxLen) {
                maxLen = len;
                // Calculate the starting index of this palindrome
                start = i - (len - 1) / 2;
            }
        }

        return s.substring(start, start + maxLen);
    }

    // Expand outward from center while chars match
    private int expand(String s, int left, int right) {

        // Keep expanding while in bounds and chars match
        while (left >= 0
            && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
            left--;    // move left pointer outward
            right++;   // move right pointer outward
        }

        // Length of palindrome found
        // (left and right have moved one step past the palindrome)
        return right - left - 1;
    }
}

func longestPalindrome(s string) string {

    // Guard: handle empty input
    if len(s) < 1 {
        return ""
    }

    // expand returns length of palindrome centered at (left, right)
    expand := func(left, right int) int {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }
        return right - left - 1
    }

    start, maxLen := 0, 0

    // Try every possible center
    for i := 0; i < len(s); i++ {

        // Odd-length palindrome: single char center
        len1 := expand(i, i)

        // Even-length palindrome: two char center
        len2 := expand(i, i+1)

        // Take the longer of the two expansions
        curLen := len1
        if len2 > curLen { curLen = len2 }

        // Update best if this palindrome is longer
        if curLen > maxLen {
            maxLen = curLen
            // Calculate the starting index of this palindrome
            start = i - (curLen-1)/2
        }
    }

    return s[start : start+maxLen]
}

def longest_palindrome(s: str) -> str:

    # Guard: handle empty input
    if len(s) < 1:
        return ""

    start, max_len = 0, 0

    def expand(left: int, right: int) -> int:
        # Expand outward from center while chars match
        while left >= 0 \
                and right < len(s) \
                and s[left] == s[right]:
            left -= 1    # move left pointer outward
            right += 1   # move right pointer outward
        # (left and right have moved one step past the palindrome)
        return right - left - 1

    # Try every possible center
    for i in range(len(s)):

        # Odd-length palindrome: single char center
        len1 = expand(i, i)

        # Even-length palindrome: two char center
        len2 = expand(i, i + 1)

        # Take the longer of the two expansions
        cur_len = max(len1, len2)

        # Update best if this palindrome is longer
        if cur_len > max_len:
            max_len = cur_len
            # Calculate the starting index of this palindrome
            start = i - (cur_len - 1) // 2

    return s[start:start + max_len]

impl Solution {
    pub fn longest_palindrome(s: String) -> String {

        // Guard: handle empty input
        if s.is_empty() { return String::new(); }

        let b = s.as_bytes();
        let n = b.len();

        // expand returns length of palindrome centered at (left, right)
        let expand = |mut left: i32, mut right: i32| {
            while left >= 0
                && right < n as i32
                && b[left as usize] == b[right as usize]
            {
                left -= 1;
                right += 1;
            }
            (right - left - 1) as usize
        };

        let mut start = 0;
        let mut max_len = 0;

        // Try every possible center
        for i in 0..n {

            // Odd-length palindrome: single char center
            let len1 = expand(i as i32, i as i32);

            // Even-length palindrome: two char center
            let len2 = expand(i as i32, i as i32 + 1);

            // Take the longer of the two expansions
            let cur_len = len1.max(len2);

            // Update best if this palindrome is longer
            if cur_len > max_len {
                max_len = cur_len;
                start = i - (cur_len - 1) / 2;
            }
        }

        s[start..start + max_len].to_string()
    }
}

function longestPalindrome(s: string): string {

    // Guard: handle empty input
    if (s.length < 1) return "";

    let start = 0, maxLen = 0;

    // Expand outward from center while chars match
    function expand(left: number, right: number): number {
        while (left >= 0
            && right < s.length
            && s[left] === s[right]) {
            left--;    // move left pointer outward
            right++;   // move right pointer outward
        }
        // (left and right have moved one step past the palindrome)
        return right - left - 1;
    }

    // Try every possible center
    for (let i = 0; i < s.length; i++) {

        // Odd-length palindrome: single char center
        const len1 = expand(i, i);

        // Even-length palindrome: two char center
        const len2 = expand(i, i + 1);

        // Take the longer of the two expansions
        const len = Math.max(len1, len2);

        // Update best if this palindrome is longer
        if (len > maxLen) {
            maxLen = len;
            // Calculate the starting index of this palindrome
            start = i - Math.floor((len - 1) / 2);
        }
    }

    return s.slice(start, start + maxLen);
}

⚡

Why right - left - 1? When the while loop exits, left and right have each moved one step beyond the palindrome boundaries. So the actual palindrome spans from left+1 to right-1, giving length (right-1) - (left+1) + 1 = right - left - 1.

📝

Why start = i - (len - 1) / 2? The center is at index i. For a palindrome of length len, the left edge is (len-1)/2 positions before the center. Integer division handles both odd and even lengths correctly.

Step 06

Interactive Demo

Enter a string and step through the expand-around-center algorithm. Watch both odd and even expansions at each center.

⚙ Expand-Around-Center Visualizer

string

Step 07

Complexity Analysis

Time

O(n²)

Space

O(n^2)

We iterate through 2n - 1 possible centers (n single-character + n-1 gap centers), and each expand call can extend up to O(n) in the worst case (e.g., "aaa...a" where every center expands to the boundaries). No extra arrays, matrices, or hash maps are needed — just a few integer variables (start, maxLen, left, right) to track the best palindrome, giving O(1) auxiliary space.

Approach Breakdown

BRUTE FORCE

O(n3) time

O(1) space

Two nested loops enumerate O(n²) substrings, and each one is compared character-by-character in O(n) to verify it reads the same forwards and backwards. No auxiliary data structures are needed.

DP TABLE

O(n2) time

O(n2) space

A boolean table dp[i][j] caches whether substring s[i..j] is a palindrome. Each cell is filled in O(1) by checking the outer characters plus dp[i+1][j-1]. The table itself has n² entries.

EXPAND CENTER

O(n2) time

O(1) space

Each of 2n-1 centers triggers an outward expansion that grows while characters match. In the worst case (all identical characters) each expansion reaches O(n), giving O(n²) total. Only a few integer variables are needed.

MANACHER'S

O(n) time

O(n) space

Reuses previously computed palindrome radii via mirror symmetry, so most centers skip expansion entirely. An auxiliary array of length 2n+1 stores the radius at each center, amortizing total work to O(n).

🎯

Expand-around-center hits the sweet spot: it matches the DP table in O(n²) time but uses O(1) space instead of an n-by-n boolean matrix. Manacher's algorithm achieves O(n) by reusing previously computed palindrome radii, but it is far more complex to implement. For interviews, expand-around-center is the expected solution — it comfortably handles n up to 1000 and is trivial to code under pressure.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.

Moving both pointers on every comparison

Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.

Usually fails on: A valid pair can be skipped when only one side should move.

Fix: Move exactly one pointer per decision branch based on invariant.

Longest PalindromicSubstring