Given a string s, return the longest substring of s that reads the same forwards and backwards.
Example
Input s = "babad"
Output "bab"
Key Pointers
Every palindrome has a center — either a single character (odd length) or a gap between two characters (even length). Expanding outward from every possible center finds them all.
There are 2n − 1 centers for a string of length n (n single-character centers, n−1 between-character ones) — checking every one is still just O(n²).
Track the best (start, length) found so far instead of slicing a new string on every expansion, to avoid unnecessary copies.
Step-by-Step Analysis
Write a helper that, given a left and right pointer, expands outward while the characters match, then reports the (start, length) of the palindrome found.
For each index i, expand around the odd center (left = i, right = i) and the even center (left = i, right = i+1).
After each expansion, compare its length to the best found so far and keep the longer one.
Return the substring described by the best (start, length) across every center.
Complexity
Time: O(n²) — Space: O(1) extra, excluding the returned substring
Code
def longestPalindrome(s: str) -> str:
start, best_len = 0, 0
def expand(left: int, right: int) -> None:
nonlocal start, best_len
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
length = right - left - 1
if length > best_len:
best_len = length
start = left + 1
for i in range(len(s)):
expand(i, i)
expand(i, i + 1)
return s[start : start + best_len]
Code Explanation
How the solution above works, piece by piece.
Every palindrome mirrors around a centre: a single character (odd length) or the gap between two characters (even length).
For each index, expand(i, i) and expand(i, i + 1) try both kinds of centre.
expand grows outward while the characters on both sides match; when it stops, the palindrome is s[left+1 : right], of length right - left - 1.
Keep the start and length of the longest one found.
2n centres × up to n expansion each: O(n²) time, O(1) space.
Visual Walkthrough
Running it on s = "babad":
Only the expansions that set a new record are shown. Centre 1 expands to "bab" (length 3); centre 2 finds "aba", also length 3, which doesn't beat it, so "bab" is returned.