Given a string of up to 1000 letters and digits, return any longest substring that reads the same forwards and backwards — testing mirrors from the middle beats re-checking every pair from the outside.
Every palindrome has a center — expand from each one and keep the widest mirror that survives.
A palindrome is fully decided by its middle: fix a center, then walk both ends outward while the pair matches. There are only 2n−1 centers — one on each character (odd lengths) and one in each gap (even lengths) — so trying all of them covers every possible answer, and the outward walk never needs to re-examine an inner pair.
Step through “babad”. Each frame compares one outer pair (l, r) around a center; green cells are a surviving mirror, red cells are the mismatch that stops a center, and the lime underline always marks the best window found so far.
class Solution:
def longestPalindrome(self, s: str) -> str:
best_l, best_r = 0, 0 # inclusive bounds of the widest mirror yet
def expand(l, r):
nonlocal best_l, best_r
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l > best_r - best_l: # strictly longer wins
best_l, best_r = l, r
l -= 1
r += 1
for i in range(len(s)):
expand(i, i) # odd: middle is s[i]
expand(i, i + 1) # even: middle is the gap i|i+1
return s[best_l:best_r + 1]The displayed Python and the trace above share one rule: compare the outer pair, keep strictly-longer windows, stop a center at its first mismatch.
expand(i, i)Starts as the single character s[i] — always a length-1 palindrome — then grows to 3, 5, 7… until the outer pair differs or an end falls off.expand(i, i + 1)Starts as a length-0 gap. If s[i] ≠ s[i+1] it contributes nothing (as in “babad”); if equal it seeds a length-2 mirror like the “bb” in “cbbd”.if r - l > best_r - best_lStrictly-longer replacement keeps the earliest longest answer on ties, matching the judge. Bounds stay inclusive, so the slice adds +1.Odd center 1 grows b·a·b to width 3; every even gap mismatches at once. The trace's first lime upgrade happens at that frame — either accepted answer proves ties keep the earliest.
All odd centers stall at width 1, but the even gap 1|2 seeds “bb” and then dies on c vs d. Single character “a” is the edge: both loops still run, best stays s[0:1].
I try every center — each character for odd lengths, each gap for even — expand while the outer pair matches, and track the widest window with constant extra space. That is quadratic time; Manacher's reuses mirror symmetry to make it linear, which I can sketch as a follow-up.