Longest Palindromic Substring
Return the longest contiguous substring of s that reads the same forwards and backwards.
Open on LeetCode ↗Intuition
Expand around centres — everyone gets that far. The mistake is treating each character as a centre and stopping there, giving n centres. Run that on 'abba' and it returns 'a': there is no middle character to grow from, because the palindrome's mirror line falls in the gap between the two b's. Even-length palindromes have no central character, and half of all palindromes are even-length, so you have blinded yourself to half the answer space. There are 2n-1 centres, not n: each of the n characters, and each of the n-1 gaps between adjacent characters. Handle a gap by starting the two pointers at i and i+1 instead of both at i — the expansion loop is otherwise identical, which is why the fix costs one extra call per index and no new logic. The invariant is that every palindromic substring has exactly one centre, so sweeping all 2n-1 centres and pushing outward while the mirrored characters match is guaranteed to encounter the longest one.
Every palindrome has a centre, and there are 2n - 1 of them — n characters plus n - 1 gaps between them. Expanding outward from each covers both odd and even lengths in O(n²) time with no table at all.
Approach
Enumerate 2n-1 centres, not n
For each index i, run the expansion twice: once with left = right = i, which grows odd-length palindromes around the character itself, and once with left = i and right = i + 1, which grows even-length palindromes around the gap to its right. The second call is the whole fix. The right = i + 1 case naturally does nothing when i is the last index or when the two characters differ, so it needs no special guard.
Expand while the mirrors match
From a centre, step left back and right forward as long as both stay in bounds and s[left] == s[right]. The moment either condition fails you have the widest palindrome for that centre, because any wider one would have to contain this mismatch. On exit the pointers have overshot by one on each side, so the substring is s[left+1:right], a detail worth writing down once rather than rederiving under time pressure.
Track indices, not strings
Keep only the start and length of the best palindrome found so far and slice once at the end. Building and comparing substring objects inside the loop turns an O(1) comparison into an O(n) copy and quietly makes the whole thing O(n^3). Comparing lengths is enough to decide whether to update.
Solution & live demo
Common pitfalls
Only expanding from character centres
for i in range(len(s)):
expand(i, i)expand(i, i) expand(i, i + 1)
Even-length palindromes like "abba" are centred on the gap between two characters, not on a character. Checking only odd centres misses every even-length answer.
Computing the length after the loop incorrectly
best = r - l + 1
best = r - l - 1
The while loop exits one step past the valid range on both sides, so the true palindrome spans l+1 to r-1 — a length of r - l - 1. Using the inclusive formula overstates it by two.
Building a full DP table
dp = [[False] * n for _ in range(n)]
for i in range(len(s)):
expand(i, i)The DP is also O(n²) in time but adds O(n²) space, which fails on long strings. Centre expansion needs only two indices.
Edge cases
The odd expansion from index 0 gives length 1 and no even centre exists; the answer is 'a'.
Every expansion stops immediately, so the best remains the first character — any single character is a valid palindrome.
Found only by the gap centre between indices 1 and 2 — this is exactly the case the character-only version misses.
The centre nearest the middle expands to the full width; boundary checks stop it at the string ends rather than running off.