• 1 <= s.length <= 1000
• s consists of digits and English letters

We are looking for the longest contiguous run inside s that reads the same forwards and backwards — a palindrome like "racecar" or "abba". Contiguous matters: the characters must be adjacent, so this is a substring, not a subsequence. If several palindromes tie for the longest, any one of them is acceptable, and since the string has at least one character the answer is never empty — a single character is trivially a palindrome.

The head-on approach: generate every substring, test each for the palindrome property, and remember the longest that passes. A string of length N has about N²/2 substrings (choose a start and an end), and checking whether one of length L reads the same both ways compares about L/2 pairs — up to O(N) work. Multiplying, that is roughly O(N³): for N = 1000 the count already reaches hundreds of millions of character comparisons.

best = ""
for i in range(len(s)):
    for j in range(i, len(s)):
        sub = s[i : j + 1]
        if sub == sub[::-1] and len(sub) > len(best):
            best = sub

The waste is glaring once named: these substrings overlap enormously, so we re-verify shared interiors over and over. Testing "abcba" reproves that "bcb" is a palindrome, which reproves "c" — work we already did while checking the shorter substrings, thrown away each time.

Here is the reframe that removes the whole third factor. Every palindrome has a center and is symmetric about it — so instead of picking two endpoints and checking inward, pick a center and grow outward. Start from the middle and step both pointers away from the center as long as the two characters they land on are equal. The moment they differ, or a pointer falls off the string, the widest palindrome around that center is exactly what you just spanned.

There is one wrinkle: a palindrome can have two kinds of center. An odd-length palindrome like "aba" is centered on a single character (the 'b'). An even-length palindrome like "abba" has no middle character — it is centered on the gap between the two b's. Every palindrome is one or the other, so the possible centers are the N characters plus the N-1 gaps between them: 2N - 1 centers. Expanding from all of them covers every palindrome that can exist.

At each index we run two expansions: one treating the character itself as the center (odd length), one treating the gap just after it as the center (even length). Each expansion walks outward in O(N); doing this at all 2N - 1 centers is O(N²) time, and it needs only a few pointers — O(1) extra space, beating the dynamic-programming table that reaches the same time bound but spends O(N²) memory to do it.

def longest_palindrome(s):
    best = ""
    for i in range(len(s)):
        odd = expand(s, i, i)       # center on the character
        even = expand(s, i, i + 1)  # center on the gap after it
        best = max(best, odd, even, key=len)
    return best

def expand(s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l + 1 : r]             # loop overshot by one on each side

There is an O(N) algorithm, Manacher's, that reuses the symmetry of palindromes already found to skip most of the expansion work — the same spirit as KMP reusing matched prefixes in substring search. It is genuinely linear but fiddly to implement correctly, and at this problem's limit (N ≤ 1000) the O(N²) center expansion is already fast and is what interviewers expect. Know that Manacher exists and roughly why it works; reach for it only when linear time is actually required.

We paid O(N²) time but bought back the entire O(N) palindrome-check factor and, versus DP, all O(N²) of the memory — by counting from centers outward instead of endpoints inward. The reusable reflex: when a problem is about symmetry around a point — longest palindrome, counting palindromic substrings, mirror structures — stop enumerating pairs of endpoints and start enumerating centers, remembering the odd/even split. It is the same mirror idea you used to verify a single palindrome in Valid Palindrome, now turned into a search over every possible center.