Longest Palindromic Substring

Given a string, return the longest palindromic substring — a contiguous span that reads identically forward and backward. There are O(n²) substrings, and checking each is O(n), so the naive solution is cubic.

The key insight: every palindrome is symmetric around a center, and there are only 2n − 1 centers — each character position and each gap between characters. Expanding outward from a center costs O(n) in the worst case, which beats checking every substring. The gap centers are what capture even-length palindromes like "bb" in "cbbd".

Approach:

1. Treat every index as a single-character center and every adjacent pair as a two-character center.
2. For each center, expand outward while the mirrored characters match.
3. Track the longest span found.

def longest_palindrome(s):
    best = ""
    for center in range(len(s)):
        for lo, hi in (center, center), (center, center + 1):
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
                lo, hi = lo - 1, hi + 1
            if hi - lo - 1 > len(best):
                best = s[lo + 1:hi]
    return best

Time: O(n²). Space: O(1).

Trickiest edge case: even-length palindromes — if the machine only expands around character centers, "cbbd" yields "b" instead of "bb"; the inter-character centers are mandatory, not an optimization.