Given a string s, return the longest palindromic substring.
A palindrome reads the same forwards and backwards. The expand-around-center approach
exploits the fact that every palindrome has a center — either a single character (odd-length) or a gap
between two characters (even-length). Try all 2n−1 centers and expand outward while
characters match. Stop the moment they differ.
examples
s = "racecar" → center 'e' expands to cover the full string → "racecar"
s = "babad" → center 'a' expands to "bab" → "bab" (also "aba")
s = "cbbd" → even center 'bb' matches → "bb"
s = "racecar" — expand around every center
best so far"r"length 1
odd centerseven centers
step 0 / 0
center
matching pair (L / R)
inside current palindrome
mismatch — stop
best palindrome
Press Next step to begin the algorithm from the first center.
State Snapshot
L
—
R
—
center
—
best
"r"
Pseudocode
time: O(n²)space: O(1)pattern: expand around center
▼ Notes & Key Insight
Key Insight
Every palindrome mirrors around a center. Fix each of the 2n−1 possible centers and expand outward — the first mismatch stops you. No need to check all O(n²) substrings explicitly.
Why 2n−1 Centers?
n centers for odd-length palindromes (each character is its own center) + n−1 centers for even-length ones (each gap between adjacent characters).
Complexity
Time: O(n²) — n centers, each expands up to O(n) in the worst case. Space: O(1) — only track the best start index and length.
Pattern
Expand Around Center. Also solvable with an O(n²) DP table (dp[i][j] = true if s[i..j] is a palindrome) or the O(n) Manacher's algorithm.
Edge Cases
• Single character → always a palindrome
• All same chars ("aaaa") → entire string is the answer
• Two chars equal ("aa") → caught by the even-center pass
vs. DP Table
The 2D DP approach also runs O(n²) but uses O(n²) space. Expand-around-center gives the same time in O(1) space — strictly better.