Palindrome Patterns

Expand Around Center

For each position in the string, treat it as the center of a potential palindrome and expand outward while characters match. Check both odd-length (single center) and even-length (two centers). O(n²).

O(n²)

O(1)

say this out loud

Palindromes are symmetric about a centre, so I expand around all 2n-1 centres to cover odd and even lengths. O(n squared) time but O(1) space.

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

Longest palindromic substring of "babad". A palindrome is defined by its centre, so try every centre and grow outward

bestb, length 1

1/9

Code

Java

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

1For each index, try it as the center of an odd-length palindrome

2Also try each pair of adjacent indices as center of even-length

3Expand outward while characters match

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.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

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

Frequently Asked Questions

Why must I check both odd and even centers?

Odd-length palindromes like 'aba' center on a character, while even-length ones like 'abba' center on the gap between two characters. Skipping the even case silently misses half the candidates, which is one of the most common bugs in this problem.

When is expand-around-center preferable to the DP table?

Both are O(n²) time, but expansion uses O(1) space versus the DP's O(n²) table, and it tends to be faster in practice because it stops early at mismatches. Reach for the DP formulation only when the problem needs palindrome lookups for arbitrary (i, j) pairs later.