Longest Palindromic Substring (LeetCode 5)
You will see why every palindrome grows out of one of 2N - 1 centers, and why the even centers are the ones people forget.
You get one string s made of English letters and digits. A palindrome is a string that is spelled the same from left to right as from right to left, like "racecar" or "abba"; an uppercase letter and its lowercase form are different characters. A substring is a run of neighbouring characters of s, taken without skipping any.
Among all substrings of s that are palindromes, find one with the greatest length and return it. If several different substrings share that greatest length, returning any one of them is correct. A single character is always a palindrome, so the answer is never empty.
Worked Examples
s = "babad""bab"s = "cbbd""bb"⚖️Formal Constraints & Bounds
1 <= s.length <= 1000sconsist of only digits and English letters.
Why It Works & Core Invariant
Every palindrome mirrors around its middle, which is a letter or the gap between two letters, so growing outward from each of the 2N - 1 middles meets every palindrome, the longest included, without testing any substring on its own.
Real-World Scenario & Production Applications
Biology checks mirrored sequences the same way: many restriction enzymes cut DNA at sites such as GAATTC, which read the same on both strands (one strand forwards, the other backwards). Testing a candidate site means comparing matching pairs outward from its middle, exactly what expand does, with the pairing A-T and C-G in place of ==.
Step-by-Step Execution Trace Table
Input s = "cbbd" (LeetCode Example 2), starting from start, length = 0, 1:
i | odd = expand(i, i) | even = expand(i, i + 1) | max(odd, even) > length? | start, length after |
|---|---|---|---|---|
| 0 | "c", then lo = -1: stop -> 1 | "c" vs "b": stop -> 0 | 1 > 1: No | 0, 1 |
| 1 | "b", then "c" vs "b": stop -> 1 | "bb", then "c" vs "d": stop -> 2 | 2 > 1: Yes | start = 1 - (2 - 1) // 2 = 1, 2 |
| 2 | "b", then "b" vs "d": stop -> 1 | "b" vs "d": stop -> 0 | 1 > 2: No | 1, 2 |
| 3 | "d", then hi = 4 = n: stop -> 1 | hi = 4 = n: stop -> 0 | 1 > 2: No | 1, 2 |
| End | return s[1:3] = "bb" |
Only the even center at i = 1 finds the answer: with expand(i, i) alone the result would stay "c".
| 1 | A palindrome is a mirror, so it is fixed by its middle: grow outward from each middle instead of testing every substring on its own. |
| 2 | `expand(lo, hi)` keeps `s[lo + 1:hi]` a palindrome: while `lo >= 0`, `hi < n` and `s[lo] == s[hi]`, step `lo` left and `hi` right; then `return hi - lo - 1`. |
| 3 | `start, length = 0, 1`; `for i in range(n):` get `odd` and `even` from two `expand` calls; if `max(odd, even) > length`, update `length` and `start = i - (length - 1) // 2`; `return s[start:start + length]`. |
| 4 | The trap: a middle can be a gap. Call `expand(i, i + 1)` as well as `expand(i, i)`, or `"cbbd"` returns `"c"` instead of `"bb"`. |
Target: Longest Palindromic Substring (LeetCode 5). Two integers describe the longest palindrome found so far; one letter is always a palindrome, so the answer starts as s[0:1]. The substring is sliced once, at the end.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A palindrome is a mirror: the first letter equals the last, the second equals the second-to-last, and so on toward the middle. Read the other way round, a palindrome is built outward from its middle, one matching pair of letters at a time. So you never need to test a substring on its own: stand on each possible middle, step outward while the two end letters match, and you meet every palindrome around that middle, from the shortest to the longest. A middle is either a letter ("aba", odd length) or the gap between two letters ("abba", even length), so a string of n letters has 2n - 1 middles.
🏟️ The Analogy: Ripples From a Stone
Drop a stone in a pond and the ripple spreads the same distance in every direction. Expanding a palindrome is a ripple on the string: each step pushes both edges out by one letter, and the ripple dies the moment the two edges see different letters. Dropping the stone on every letter is not enough: some ripples start between two letters, and those are the even palindromes.
🪄 The Mathematical Harmony / Magic Trick
def expand(lo, hi): while lo >= 0 and hi < n and s[lo] == s[hi]: lo -= 1 # grow one letter on each side hi += 1 return hi - lo - 1 # one step past each end for i in range(n): odd = expand(i, i) # middle = the letter s[i] even = expand(i, i + 1) # middle = the gap after s[i] The loop overshoots: it stops at the first pair that does not match (or at the edge), so the palindrome is s[lo + 1:hi] and its length is hi - lo - 1. And there are two calls for every i: "cbbd" has no odd palindrome longer than one letter, and its answer "bb" is only found from the gap between the two bs.
💡 Summary
Every palindrome has one middle; try all 2n - 1 of them, letters and gaps, grow each while the ends match, and keep the longest. No substring is ever tested on its own.
Only odd centers: call
expand(i, i + 1)besideexpand(i, i)."bb"in"cbbd"is centered on the gap between two letters, and the odd call alone returns"c".The length after the loop: the
whilestops one step past each end, so the palindrome iss[lo + 1:hi]and its length ishi - lo - 1, nothi - lo + 1.The start of an even palindrome:
start = i - (length - 1) // 2works for both centers;i - length // 2starts one letter early on even lengths ("cbbd"gives"cb").A missing bound: test
lo >= 0 and hi < nbefores[lo] == s[hi]. In Pythons[-1]is the last letter, so a missinglo >= 0compares the wrong letters without raising an error.Testing every substring: checking each of the about N^2 / 2 substrings by reversing it is O(N^3); growing from the 2N - 1 centers is O(N^2).
4-Phase Thought Process Model
You will see how a senior engineer turns "longest palindromic substring" into 2N - 1 small expansions, and names the center everyone forgets.
Pattern Recognition Signals
The 10-second spot
"Longest palindromic substring": a substring is a run of neighbouring letters, and a palindrome is a mirror, so each one is fixed by its middle and grows outward one matching pair at a time. With s.length <= 1000, trying every middle and growing from it (quadratic) fits, while testing every substring on its own (cubic) does not. That is the Longest Palindromic Substring move: expand around every center.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Inside expand(lo, hi), s[lo + 1:hi] is always a palindrome: the loop adds one letter on each side while lo >= 0, hi < n and s[lo] == s[hi], and return hi - lo - 1 gives the length it grew. After center i, s[start:start + length] is the longest palindrome around any center up to i.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
even = expand(i, i + 1): an even palindrome such as"bb"has no middle letter; with onlyexpand(i, i),"cbbd"returns"c".return hi - lo - 1: the loop stops one step past each end, so the palindrome iss[lo + 1:hi];hi - lo + 1also counts the two letters that did not match.start = i - (length - 1) // 2: the same formula serves both centers;i - length // 2starts one letter too early on an even palindrome ("cbbd"gives"cb").while lo >= 0 and hi < n and s[lo] == s[hi]: check both bounds before readings[lo]. In Pythons[-1]is the last letter, so a missinglo >= 0compares the wrong letters without any error.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Expand Around Center, the standard Longest Palindromic Substring move. A palindrome is a mirror, so it is fixed by its middle, and the middle is either a letter or the gap between two letters. That gives 2N minus 1 centers. From each one I grow outward: while the two end letters match and stay inside the string, I step one to the left and one to the right. When the loop stops it is one step past each end, so the palindrome's length is hi minus lo minus 1. I keep the best start and length, and slice once at the end. The trap is the even centers: "bb" has no middle letter, so for every i I expand from i, i and from i, i plus 1. With the odd call alone, "cbbd" returns "c". Each expansion takes at most N steps, so it's O(N squared) time and
O(1)extra space.
So: expand from every letter and every gap; hi - lo - 1 is the length; the trap is skipping expand(i, i + 1).
Complexity & Mathematical Proof
O(N^2)
Look at the code: for i in range(n) runs N times and makes two calls, expand(i, i) and expand(i, i + 1). Each step of the while loop moves lo one left and hi one right, and the loop stops once either end leaves the string, so a call around center i runs at most min(i, N - 1 - i) + 1 steps, never more than about N / 2. Two calls per i over N values of i is at most about N^2 / 2 steps in all: O(N^2). The max, the comparison with length and the start update are O(1) per center, and the final slice s[start:start + length] copies at most N letters once.
O(1)
The scan keeps a fixed set of integers: n, start, length, i, odd, even, and lo, hi inside expand. Each expand call returns before the next one starts, so the call stack never goes deeper than one call: O(1) extra space. The returned substring holds up to N characters; it is the output and is not counted.
T(N) = Σ_{i=0}^{N-1} [steps of expand(i, i) + steps of expand(i, i + 1)] ≤ 2N · (N / 2 + 1) = O(N^2)
Look at the code: for i in range(n) runs N times and makes two calls, expand(i, i) and expand(i, i + 1). Each step of the while loop moves lo one left and hi one right, and the loop stops once either end leaves the string, so a call around center i runs at most min(i, N - 1 - i) + 1 steps, never more than about N / 2. Two calls per i over N values of i is at most about N^2 / 2 steps in all: O(N^2). The max, the comparison with length and the start update are O(1) per center, and the final slice s[start:start + length] copies at most N letters once.
Derivation Progression
N iterations, 2 calls each
for i in range(n) calls expand(i, i) (odd lengths) and expand(i, i + 1) (even lengths): 2N calls, 2N - 1 of them at a real center.
≤ min(i, N - 1 - i) + 1 steps
Each while step moves lo down and hi up by one, and the loop ends when either leaves the string or the letters differ.
O(1) per center
max(odd, even) > length, then at most two assignments to length and start.
≤ 2N · (N / 2 + 1) = O(N^2)
The expansions dominate; the single slice at the end adds only O(N).
Variable Definitions
Length of s, n = len(s) (1 to 1000)
The center being expanded: the letter s[i] for expand(i, i), the gap after it for expand(i, i + 1)
The two ends inside expand; s[lo + 1:hi] is always a palindrome
Memory Architecture & Bounds
O(1): expand is one call deep and returns before the next call
O(1): n, start, length, i, odd, even, lo, hi
O(N): the returned substring (not counted)
Boundary Best / Worst Cases
: no two neighbouring letters are equal and no letter has equal neighbours (for example all letters distinct), so every expansion stops after at most one step
bound; on random text most expansions stop after a step or two, so the scan runs close to
: every letter is the same ("aaaa..."), so every center grows to the nearer end of the string, about steps
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest palindromic substring", "s.length <= 1000". A run of letters that mirrors is fixed by its middle: Expand Around Center from all middles instead of testing every substring.
letters and digits. Testing every substring by reversing it is , about character steps at the limit; growing from each center is , at most about steps, with extra space.
Skipping the even centers (expand(i, i + 1)) loses every even palindrome. At scale: building a new substring for every candidate turns an -space scan into heavy allocation, so keep two integers and slice once; on Unicode text, mirror code points (or grapheme clusters), not UTF-8 bytes, because a multi-byte character reversed byte by byte is no longer the same character; for inputs far past characters, is too slow, and Manacher's algorithm reaches by reusing the mirror image of expansions it has already finished.
Core Algorithmic State Invariants
Removing both end letters of a palindrome leaves a palindrome with the same middle, so `expand(lo, hi)` meets every palindrome around a center, shortest first, and the first mismatch ends them all.
A middle is a letter, `expand(i, i)` (odd lengths), or the gap after it, `expand(i, i + 1)` (even lengths). Skipping the gap loses `"bb"` in `"cbbd"`.
Every center grows at most to the nearer end of `s`, so the scan is O(N^2) time; `start` and `length` are two integers, so the extra space is O(1).
Longest Palindromic Substring (LeetCode 5)
You will see why every palindrome grows out of one of 2N - 1 centers, and why the even centers are the ones people forget.
You get one string s made of English letters and digits. A palindrome is a string that is spelled the same from left to right as from right to left, like "racecar" or "abba"; an uppercase letter and its lowercase form are different characters. A substring is a run of neighbouring characters of s, taken without skipping any.
Among all substrings of s that are palindromes, find one with the greatest length and return it. If several different substrings share that greatest length, returning any one of them is correct. A single character is always a palindrome, so the answer is never empty.
Worked Examples
s = "babad""bab"s = "cbbd""bb"⚖️Formal Constraints & Bounds
1 <= s.length <= 1000sconsist of only digits and English letters.
Why It Works & Core Invariant
Every palindrome mirrors around its middle, which is a letter or the gap between two letters, so growing outward from each of the 2N - 1 middles meets every palindrome, the longest included, without testing any substring on its own.
Real-World Scenario & Production Applications
Biology checks mirrored sequences the same way: many restriction enzymes cut DNA at sites such as GAATTC, which read the same on both strands (one strand forwards, the other backwards). Testing a candidate site means comparing matching pairs outward from its middle, exactly what expand does, with the pairing A-T and C-G in place of ==.
Step-by-Step Execution Trace Table
Input s = "cbbd" (LeetCode Example 2), starting from start, length = 0, 1:
i | odd = expand(i, i) | even = expand(i, i + 1) | max(odd, even) > length? | start, length after |
|---|---|---|---|---|
| 0 | "c", then lo = -1: stop -> 1 | "c" vs "b": stop -> 0 | 1 > 1: No | 0, 1 |
| 1 | "b", then "c" vs "b": stop -> 1 | "bb", then "c" vs "d": stop -> 2 | 2 > 1: Yes | start = 1 - (2 - 1) // 2 = 1, 2 |
| 2 | "b", then "b" vs "d": stop -> 1 | "b" vs "d": stop -> 0 | 1 > 2: No | 1, 2 |
| 3 | "d", then hi = 4 = n: stop -> 1 | hi = 4 = n: stop -> 0 | 1 > 2: No | 1, 2 |
| End | return s[1:3] = "bb" |
Only the even center at i = 1 finds the answer: with expand(i, i) alone the result would stay "c".
| 1 | A palindrome is a mirror, so it is fixed by its middle: grow outward from each middle instead of testing every substring on its own. |
| 2 | `expand(lo, hi)` keeps `s[lo + 1:hi]` a palindrome: while `lo >= 0`, `hi < n` and `s[lo] == s[hi]`, step `lo` left and `hi` right; then `return hi - lo - 1`. |
| 3 | `start, length = 0, 1`; `for i in range(n):` get `odd` and `even` from two `expand` calls; if `max(odd, even) > length`, update `length` and `start = i - (length - 1) // 2`; `return s[start:start + length]`. |
| 4 | The trap: a middle can be a gap. Call `expand(i, i + 1)` as well as `expand(i, i)`, or `"cbbd"` returns `"c"` instead of `"bb"`. |
Target: Longest Palindromic Substring (LeetCode 5). Two integers describe the longest palindrome found so far; one letter is always a palindrome, so the answer starts as s[0:1]. The substring is sliced once, at the end.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A palindrome is a mirror: the first letter equals the last, the second equals the second-to-last, and so on toward the middle. Read the other way round, a palindrome is built outward from its middle, one matching pair of letters at a time. So you never need to test a substring on its own: stand on each possible middle, step outward while the two end letters match, and you meet every palindrome around that middle, from the shortest to the longest. A middle is either a letter ("aba", odd length) or the gap between two letters ("abba", even length), so a string of n letters has 2n - 1 middles.
🏟️ The Analogy: Ripples From a Stone
Drop a stone in a pond and the ripple spreads the same distance in every direction. Expanding a palindrome is a ripple on the string: each step pushes both edges out by one letter, and the ripple dies the moment the two edges see different letters. Dropping the stone on every letter is not enough: some ripples start between two letters, and those are the even palindromes.
🪄 The Mathematical Harmony / Magic Trick
def expand(lo, hi): while lo >= 0 and hi < n and s[lo] == s[hi]: lo -= 1 # grow one letter on each side hi += 1 return hi - lo - 1 # one step past each end for i in range(n): odd = expand(i, i) # middle = the letter s[i] even = expand(i, i + 1) # middle = the gap after s[i] The loop overshoots: it stops at the first pair that does not match (or at the edge), so the palindrome is s[lo + 1:hi] and its length is hi - lo - 1. And there are two calls for every i: "cbbd" has no odd palindrome longer than one letter, and its answer "bb" is only found from the gap between the two bs.
💡 Summary
Every palindrome has one middle; try all 2n - 1 of them, letters and gaps, grow each while the ends match, and keep the longest. No substring is ever tested on its own.
Only odd centers: call
expand(i, i + 1)besideexpand(i, i)."bb"in"cbbd"is centered on the gap between two letters, and the odd call alone returns"c".The length after the loop: the
whilestops one step past each end, so the palindrome iss[lo + 1:hi]and its length ishi - lo - 1, nothi - lo + 1.The start of an even palindrome:
start = i - (length - 1) // 2works for both centers;i - length // 2starts one letter early on even lengths ("cbbd"gives"cb").A missing bound: test
lo >= 0 and hi < nbefores[lo] == s[hi]. In Pythons[-1]is the last letter, so a missinglo >= 0compares the wrong letters without raising an error.Testing every substring: checking each of the about N^2 / 2 substrings by reversing it is O(N^3); growing from the 2N - 1 centers is O(N^2).
4-Phase Thought Process Model
You will see how a senior engineer turns "longest palindromic substring" into 2N - 1 small expansions, and names the center everyone forgets.
Pattern Recognition Signals
The 10-second spot
"Longest palindromic substring": a substring is a run of neighbouring letters, and a palindrome is a mirror, so each one is fixed by its middle and grows outward one matching pair at a time. With s.length <= 1000, trying every middle and growing from it (quadratic) fits, while testing every substring on its own (cubic) does not. That is the Longest Palindromic Substring move: expand around every center.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Inside expand(lo, hi), s[lo + 1:hi] is always a palindrome: the loop adds one letter on each side while lo >= 0, hi < n and s[lo] == s[hi], and return hi - lo - 1 gives the length it grew. After center i, s[start:start + length] is the longest palindrome around any center up to i.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
even = expand(i, i + 1): an even palindrome such as"bb"has no middle letter; with onlyexpand(i, i),"cbbd"returns"c".return hi - lo - 1: the loop stops one step past each end, so the palindrome iss[lo + 1:hi];hi - lo + 1also counts the two letters that did not match.start = i - (length - 1) // 2: the same formula serves both centers;i - length // 2starts one letter too early on an even palindrome ("cbbd"gives"cb").while lo >= 0 and hi < n and s[lo] == s[hi]: check both bounds before readings[lo]. In Pythons[-1]is the last letter, so a missinglo >= 0compares the wrong letters without any error.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Expand Around Center, the standard Longest Palindromic Substring move. A palindrome is a mirror, so it is fixed by its middle, and the middle is either a letter or the gap between two letters. That gives 2N minus 1 centers. From each one I grow outward: while the two end letters match and stay inside the string, I step one to the left and one to the right. When the loop stops it is one step past each end, so the palindrome's length is hi minus lo minus 1. I keep the best start and length, and slice once at the end. The trap is the even centers: "bb" has no middle letter, so for every i I expand from i, i and from i, i plus 1. With the odd call alone, "cbbd" returns "c". Each expansion takes at most N steps, so it's O(N squared) time and
O(1)extra space.
So: expand from every letter and every gap; hi - lo - 1 is the length; the trap is skipping expand(i, i + 1).
Complexity & Mathematical Proof
O(N^2)
Look at the code: for i in range(n) runs N times and makes two calls, expand(i, i) and expand(i, i + 1). Each step of the while loop moves lo one left and hi one right, and the loop stops once either end leaves the string, so a call around center i runs at most min(i, N - 1 - i) + 1 steps, never more than about N / 2. Two calls per i over N values of i is at most about N^2 / 2 steps in all: O(N^2). The max, the comparison with length and the start update are O(1) per center, and the final slice s[start:start + length] copies at most N letters once.
O(1)
The scan keeps a fixed set of integers: n, start, length, i, odd, even, and lo, hi inside expand. Each expand call returns before the next one starts, so the call stack never goes deeper than one call: O(1) extra space. The returned substring holds up to N characters; it is the output and is not counted.
T(N) = Σ_{i=0}^{N-1} [steps of expand(i, i) + steps of expand(i, i + 1)] ≤ 2N · (N / 2 + 1) = O(N^2)
Look at the code: for i in range(n) runs N times and makes two calls, expand(i, i) and expand(i, i + 1). Each step of the while loop moves lo one left and hi one right, and the loop stops once either end leaves the string, so a call around center i runs at most min(i, N - 1 - i) + 1 steps, never more than about N / 2. Two calls per i over N values of i is at most about N^2 / 2 steps in all: O(N^2). The max, the comparison with length and the start update are O(1) per center, and the final slice s[start:start + length] copies at most N letters once.
Derivation Progression
N iterations, 2 calls each
for i in range(n) calls expand(i, i) (odd lengths) and expand(i, i + 1) (even lengths): 2N calls, 2N - 1 of them at a real center.
≤ min(i, N - 1 - i) + 1 steps
Each while step moves lo down and hi up by one, and the loop ends when either leaves the string or the letters differ.
O(1) per center
max(odd, even) > length, then at most two assignments to length and start.
≤ 2N · (N / 2 + 1) = O(N^2)
The expansions dominate; the single slice at the end adds only O(N).
Variable Definitions
Length of s, n = len(s) (1 to 1000)
The center being expanded: the letter s[i] for expand(i, i), the gap after it for expand(i, i + 1)
The two ends inside expand; s[lo + 1:hi] is always a palindrome
Memory Architecture & Bounds
O(1): expand is one call deep and returns before the next call
O(1): n, start, length, i, odd, even, lo, hi
O(N): the returned substring (not counted)
Boundary Best / Worst Cases
: no two neighbouring letters are equal and no letter has equal neighbours (for example all letters distinct), so every expansion stops after at most one step
bound; on random text most expansions stop after a step or two, so the scan runs close to
: every letter is the same ("aaaa..."), so every center grows to the nearer end of the string, about steps
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest palindromic substring", "s.length <= 1000". A run of letters that mirrors is fixed by its middle: Expand Around Center from all middles instead of testing every substring.
letters and digits. Testing every substring by reversing it is , about character steps at the limit; growing from each center is , at most about steps, with extra space.
Skipping the even centers (expand(i, i + 1)) loses every even palindrome. At scale: building a new substring for every candidate turns an -space scan into heavy allocation, so keep two integers and slice once; on Unicode text, mirror code points (or grapheme clusters), not UTF-8 bytes, because a multi-byte character reversed byte by byte is no longer the same character; for inputs far past characters, is too slow, and Manacher's algorithm reaches by reusing the mirror image of expansions it has already finished.
Core Algorithmic State Invariants
Removing both end letters of a palindrome leaves a palindrome with the same middle, so `expand(lo, hi)` meets every palindrome around a center, shortest first, and the first mismatch ends them all.
A middle is a letter, `expand(i, i)` (odd lengths), or the gap after it, `expand(i, i + 1)` (even lengths). Skipping the gap loses `"bb"` in `"cbbd"`.
Every center grows at most to the nearer end of `s`, so the scan is O(N^2) time; `start` and `length` are two integers, so the extra space is O(1).
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| The best answer so far, kept as a start and a length | start, length = 0, 1 | Two integers describe the longest palindrome found so far; one letter is always a palindrome, so the answer starts as s[0:1]. The substring is sliced once, at the end. |
| Grow one center while both ends stay inside s and match | while lo >= 0 and hi < n and s[lo] == s[hi]: | The bounds are checked before the letters, so s[lo] and s[hi] are always real positions; each passing check means s[lo:hi + 1] is a palindrome. |
| Step one letter out on each side | lo -= 1
hi += 1 | Both ends move together, so the window stays centered on the same middle. |
| The loop overshoots each end by one | return hi - lo - 1 | The loop stops at the first pair that does not match (or at the edge), so the palindrome is s[lo + 1:hi], which holds hi - lo - 1 letters. |
| Every letter and every gap is a center (the trap: the gap) | odd = expand(i, i)
even = expand(i, i + 1) | A middle is a letter (odd lengths) or the gap after it (even lengths). Without the second call, "bb" in "cbbd" is never found. |
| Keep the longer palindrome | if max(odd, even) > length:
length = max(odd, even) | A strictly longer palindrome replaces the best one; a tie keeps the earlier one, which LeetCode accepts. |
| Recover where the best palindrome starts | start = i - (length - 1) // 2 | The middle is i (odd) or the gap after i (even); the same formula gives the first index for both. |
| Slice once at the end | return s[start:start + length] | Only the final answer is copied out of s; no substring is built while searching. |