Palindrome — Expand Around Center
Every palindrome has a center — a single character (odd length) or a gap between two characters (even length). Expanding outward from every possible center in O(n) total gives the longest palindromic substring in O(n²) time, O(1) space — far simpler than Manacher's but powerful enough for almost all interviews.
Table of contents
The problem
Given a string, find the longest substring that reads the same forwards and backwards. "racecar" is a palindrome; "aceca" inside "racecareffort" is the answer.
Brute force: check every possible substring — O(n³). Better: for each center, expand — O(n²). Manacher's algorithm: O(n), but complex. The expand-around-center approach is the sweet spot for interviews.
The ripple in a pond story
A real-life story
Drop a stone in a still pond. Ripples expand symmetrically outward from the impact point. Now imagine checking: are the characters at equal distances from the center always the same? If yes, the ripple can keep growing. The moment characters differ, the palindrome ends.
Expanding around every character (and every gap between characters) in the string is like dropping a stone at each position — you find the largest symmetric ripple rooted there.
The one idea to remember
The entire pattern in one sentence
For each of the 2n−1 possible centers in a string of length n (n single characters + n−1 gaps), expand outward while characters match; track the widest palindrome found.
The skeleton
def expand(s: str, left: int, right: int) -> tuple[int, int]:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# when loop exits, s[left] != s[right] (or boundary hit)
# the palindrome is s[left+1 .. right-1]
return left + 1, right - 1
Call this for every center:
def longestPalindrome(s: str) -> str:
start, end = 0, 0
for i in range(len(s)):
# odd-length palindrome: center at character i
l1, r1 = expand(s, i, i)
# even-length palindrome: center between i and i+1
l2, r2 = expand(s, 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]
Frame-by-frame: s = "babad"
Centers and their expanded palindromes:
i=0: odd expand('b','b') → "b" [0,0]
even expand('b','a') → mismatch → ""
i=1: odd expand('a','a') → 'b'='b' → "bab" [0,2]
even expand('a','b') → mismatch → ""
i=2: odd expand('b','b') → 'a'='a' → "aba" [1,3]
even expand('b','a') → mismatch → ""
i=3: odd expand('a','a') → 'b'≠'d' → "a" [3,3]
even expand('a','d') → mismatch → ""
i=4: odd expand('d','d') → "d" [4,4]
Best: "bab" or "aba" (both length 3). Returns "bab" ✅ (first found)
Variant: Count all palindromic substrings (LC #647)
def countSubstrings(s: str) -> int:
count = 0
for i in range(len(s)):
# odd
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
l -= 1; r += 1
# even
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
l -= 1; r += 1
return count
Each expansion that succeeds counts as one palindromic substring.
When to use this vs Manacher's
| Scenario | Use |
|---|---|
| Interview — find longest palindrome | Expand Around Center (O(n²), O(1) space, simple code) |
| Competitive programming — O(n) required | Manacher's (next chapter) |
| Count all palindromic substrings | Expand Around Center works perfectly |
| Palindrome DP problems | Different pattern — use dp[i][j] table |
Common traps
Watch out for these
- Forgetting even-length palindromes. Always call
expand(i, i)ANDexpand(i, i+1). Missing the second call misses all even-length palindromes (like "abba", "noon"). - Off-by-one in result extraction. After the while loop,
leftandrightare one step past the palindrome boundary. The palindrome iss[left+1 .. right-1], nots[left .. right]. - Using only center expansion for DP problems. Palindrome DP (LC #132 minimum cuts) is a different pattern — dp[i][j] rather than expansion. Expansion doesn't give you the full palindrome table efficiently.
Remember this forever
Expand Around Center
def expand(s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return l + 1, r - 1 # palindrome is s[l+1..r-1]
for i in range(len(s)):
check expand(s, i, i) # odd-length
check expand(s, i, i+1) # even-length
Trap: always try BOTH odd and even. Result is s[left+1 : right] (inclusive right +1 for Python slicing).
Check yourself
After `expand(s, i, i)` returns `(l, r)`, why is the palindrome `s[l+1..r-1]` and not `s[l..r]`?
The while loop exits when s[left] != s[right] or a boundary is hit. At that point, left has already moved one step too far left and right one step too far right — they're outside the palindrome. The last valid matching positions were left + 1 and right - 1. So the palindrome is s[left+1 .. right-1].
Why are there exactly 2n−1 centers for a string of length n?
There are n single-character centers (one per character) for odd-length palindromes, and n−1 gap centers (between adjacent pairs) for even-length palindromes. Total: n + (n−1) = 2n−1.
Practice problems
| Problem | Difficulty | What to notice | Link |
|---|---|---|---|
| Longest Palindromic Substring | Medium | Classic — try both odd and even centers | LC #5 |
| Palindromic Substrings (count) | Medium | Count all expansions that succeed | LC #647 |
| Valid Palindrome II | Easy | Two-pointer + expand helper on mismatch | LC #680 |
Next up: Manacher's Algorithm — the O(n) palindrome algorithm that reuses previously computed palindrome radii to avoid redundant comparisons.