Expand Around Center

How It Works

Every palindrome is symmetric about a center, and a string of length n has 2n − 1 possible centers: n single characters for odd-length palindromes and n − 1 gaps between characters for even-length ones. For each center, expand two pointers outward while the characters match; the expansion halts at the first mismatch, and the widest expansion seen is the longest palindromic substring.

Each expansion costs at most O(n), so the total is O(n²) time with O(1) extra space — better than the O(n³) of checking every substring naively, and simpler than the O(n²) DP table because no memory is needed. For interview-sized inputs this is usually the expected solution.

Step-by-Step Visualization

Code

static String longestPalindrome(String s) {
  int start = 0, maxLen = 1;

  for (int i = 0; i < s.length(); i++) {
    int odd = expand(s, i, i);
    int even = expand(s, i, i + 1);
    int len = Math.max(odd, even);
    if (len > maxLen) {
      maxLen = len;
      start = i - (len - 1) / 2;
    }
  }
  return s.substring(start, start + maxLen);
}

static int expand(String s, int l, int r) {
  while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
  return r - l - 1;
}

Tips & Gotchas

Practice Problems

• 1Longest Palindromic Substring
• 2Palindromic Substrings
• 3Shortest Palindrome

About the Palindrome Patterns Pattern

A palindrome reads the same forwards and backwards. The core techniques: expand from the center outward to find palindromes, or use DP to check if substrings are palindromes.

Common String Interview Problems

• Longest Substring Without Repeating Characters
• Valid Anagram
• Longest Palindromic Substring
• Minimum Window Substring
• Group Anagrams

Frequently Asked Questions

Other Palindrome Patterns Techniques