02
Intuition
Every palindrome has a center — a character (odd length) or a gap (even length). There are only 2n−1 centers, and expanding outward from each until the mirror breaks finds the longest palindrome anchored there. Track the global best.
03
Approach
1
Enumerate centers, not substrings
Checking all O(n²) substrings each in O(n) is cubic. Centers flip the loop: 2n−1 centers × O(n) expansion = O(n²) worst case, tiny in practice.
2
Expand while mirrored
From (l, r) grow while s[l] == s[r]. On exit, s[l+1..r−1] is the maximal palindrome for that center.
3
Odd and even both
Seed (i, i) for odd and (i, i+1) for even lengths — the miss most people make.
04
Solution & live demo
python
▶1class Solution:
▶2 def longestPalindrome(self, s):
▶3 best = ""
▶4 def expand(l, r):
▶5 while l >= 0 and r < len(s) and s[l] == s[r]:
▶6 l -= 1; r += 1
▶7 return s[l+1:r]
▶8 for i in range(len(s)):
▶9 for cand in (expand(i, i), expand(i, i + 1)):
▶10 if len(cand) > len(best): best = cand
▶11 return best
05
Edge cases
All same characters
Every center expands to the ends — worst case O(n²), still correct.
No palindrome longer than 1
First character stands as the default answer.
06
Complexity
Time
O(n²)
Space
O(1)
Manacher's achieves O(n) but is rarely needed.