43. Longest Palindromic Substring

Problem

An eval harness logs the raw decoded string for every sampled completion. A known decoding bug occasionally makes the model emit a mirrored run of characters (a repetition artifact around a decoding boundary) instead of sensible text. Before triaging a batch of flagged completions by hand, the harness first extracts the longest contiguous palindromic substring in each decoded string, since a long one is a strong signal of this artifact.

If multiple substrings of the maximum length exist, return the one that starts earliest in the input string.

Source: src/43_longest_palindromic_substring.py

def longest_palindromic_substring(s: str) -> str: ...

>>> longest_palindromic_substring("babad")
'bab'

>>> longest_palindromic_substring("cbbd")
'bb'

Step-by-Step Approach

1. Notice every palindrome has a center: a single character for odd-length palindromes, or a gap between two adjacent characters for even-length ones. A string of length n has exactly 2n - 1 such centers.
2. Write an _expand(left, right) helper that grows outward from a center while the characters at left and right keep matching, then returns the last valid (in-bounds, matching) span.
3. Loop over every index as a potential center. For each one, call _expand(i, i) to check the odd-length palindrome centered there, and _expand(i, i + 1) to check the even-length palindrome centered in the gap right after it.
4. Track the best (longest) span seen so far as (best_start, best_end), updating only on a strictly longer span so the first (leftmost) maximal palindrome wins ties.
5. After trying every center, slice s[best_start:best_end + 1] and return it.

The key insight is that trying all 2n - 1 centers and growing each one outward is O(n^2) time with only O(1) extra space — no DP table is needed, because a palindrome's own symmetry means you never have to look "backwards" once you're expanding from its true center.

Reference solution

def longest_palindromic_substring(s: str) -> str:
    # expand-around-center: every palindrome has a center (a single char for
    # odd length, a gap between two chars for even length); trying all 2n-1
    # centers and growing outward is O(n^2) time, O(1) space -- no DP table needed
    if not s:
        return ""

    def _expand(left: int, right: int) -> tuple[int, int]:
        # grow outward while the two ends match, then report the last valid span
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    best_start, best_end = 0, 0
    for center in range(len(s)):
        odd_start, odd_end = _expand(center, center)  # odd-length palindromes
        if odd_end - odd_start > best_end - best_start:
            best_start, best_end = odd_start, odd_end
        even_start, even_end = _expand(center, center + 1)  # even-length palindromes
        if even_end - even_start > best_end - best_start:
            best_start, best_end = even_start, even_end

    return s[best_start:best_end + 1]

Key Functions & Tricks

• _expand(left, right) — grows a candidate palindrome outward from a center until it breaks, in one shared helper for both parities.
• Odd vs. even centers — calling the same expand helper with (i, i) and (i, i + 1) covers both palindrome parities without separate code paths.
• Tracking span length via end - start instead of materializing substrings on every comparison avoids unnecessary string allocation.
• Strict > comparison when updating the best span — keeps the earliest (leftmost) maximal palindrome on ties, matching the problem's tie-break rule.
• s[best_start:best_end + 1] — slice is only materialized once, at the very end.

How to Recognize This Pattern