Longest Palindromic Substring (LeetCode 5)
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""bab" (indices 0 to 2) and "aba" (indices 1 to 3) are both palindromes of length 3, and no longer substring is one, so either answer is accepted.s = "cbbd""bb"bs side by side form "bb", a palindrome whose middle is the gap between them.⚖️Formal Constraints & Bounds
1 <= s.length <= 1000sconsist of only digits and English letters.
Core Insight
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"`. |
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 stops the moment the two edge letters differ. Dropping the stone on every letter is not enough: some ripples start between two letters, and those are the even palindromes.
🔑 Why It Works
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.
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
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
expand(i, i + 1)besideexpand(i, i)(gotcha 1): the other gotchas are the lines ofexpandand thestartformula.Any one longest palindrome is accepted: for
"babad"both"bab"and"aba"are right, so keep the first longest found instead of collecting them all.shas at least one letter and a single letter is a palindrome, sostart, length = 0, 1is a valid answer before any expansion: the result is never empty.
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 about N over 2 steps, so it's O(N squared) time and
O(1)extra space.
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)
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.
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
- Reversing
sIs a Wrong Turn
The longest common substring of s and its reverse is not always a palindrome: for "abacdfgdcaba" it is "abacd", which is not one. Growing from each middle only ever builds real palindromes, so there is nothing to check afterwards.
Longest Palindromic Substring (LeetCode 5)
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""bab" (indices 0 to 2) and "aba" (indices 1 to 3) are both palindromes of length 3, and no longer substring is one, so either answer is accepted.s = "cbbd""bb"bs side by side form "bb", a palindrome whose middle is the gap between them.⚖️Formal Constraints & Bounds
1 <= s.length <= 1000sconsist of only digits and English letters.
Core Insight
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"`. |
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 stops the moment the two edge letters differ. Dropping the stone on every letter is not enough: some ripples start between two letters, and those are the even palindromes.
🔑 Why It Works
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.
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
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
expand(i, i + 1)besideexpand(i, i)(gotcha 1): the other gotchas are the lines ofexpandand thestartformula.Any one longest palindrome is accepted: for
"babad"both"bab"and"aba"are right, so keep the first longest found instead of collecting them all.shas at least one letter and a single letter is a palindrome, sostart, length = 0, 1is a valid answer before any expansion: the result is never empty.
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 about N over 2 steps, so it's O(N squared) time and
O(1)extra space.
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)
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.
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
- Reversing
sIs a Wrong Turn
The longest common substring of s and its reverse is not always a palindrome: for "abacdfgdcaba" it is "abacd", which is not one. Growing from each middle only ever builds real palindromes, so there is nothing to check afterwards.