49. Longest Palindromic Fragment

Problem

A lighter, more abstract warm-up: given a normalized (lowercased, whitespace-stripped) query string, find the longest contiguous fragment that reads the same forwards and backwards. This is a pure string-DP / two-pointer practice problem, loosely framed as a Fin string-processing exercise rather than tied to any specific Fin behavior.

If multiple fragments tie for the longest length, return the earliest-starting one. An empty input string returns an empty string.

Source: src/49_longest_palindromic_query_fragment.py

def longest_palindrome(s: str) -> str:

>>> longest_palindrome(s="babad")
'bab'

>>> longest_palindrome(s="cbbd")
'bb'

Step-by-Step Approach

1. Handle the empty-string edge case up front, returning "" immediately.
2. A palindrome is symmetric around some center. That center is either a single character (odd-length palindrome) or the gap between two adjacent characters (even-length palindrome) — so every possible palindrome has exactly one of 2n - 1 possible centers for a string of length n.
3. Write an expand(left, right) helper that starts at a candidate center and grows outward one step at a time while s[left] == s[right], stopping as soon as the characters mismatch or a boundary is hit. It returns the widest matching span found.
4. Loop over every index i from 0 to len(s) - 1, calling expand(i, i) for the odd-length case centered on i, and expand(i, i + 1) for the even-length case centered between i and i + 1.
5. Track the best (longest) span seen so far across all centers, keeping the first-found span on ties since iteration proceeds left to right.
6. Return the substring corresponding to the best span found.

The key insight is that checking all 2n - 1 centers and expanding outward from each is O(n²) total but far simpler to implement correctly than the O(n) Manacher's algorithm, and is the expected approach for a medium-difficulty interview question.

Reference solution

def longest_palindrome(s: str) -> str:
    # expand around each center (odd and even length), O(n^2) time, O(1) space
    if not s:
        # empty-string edge case
        return ""

    # closure over s, grows outward while chars match
    def expand(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # +1/-1 corrects for the one-step overshoot past the mismatch
        return left + 1, right - 1

    best_start, best_end = 0, 0
    for i in range(len(s)):
        # odd-length center: single character
        l1, r1 = expand(i, i)
        # strict > keeps the earliest span on ties
        if r1 - l1 > best_end - best_start:
            best_start, best_end = l1, r1
        # even-length center: gap between two characters
        l2, r2 = expand(i, i + 1)
        if r2 - l2 > best_end - best_start:
            best_start, best_end = l2, r2
    # +1 since best_end is an inclusive index
    return s[best_start : best_end + 1]

Key Functions & Tricks

• def expand(left, right) -> tuple[int, int]: — closure helper, grows outward one step at a time while characters match.
• Two center types (odd vs. even) — every palindrome centers on a character or a gap; checking both covers all 2n - 1 centers.
• if r1 - l1 > best_end - best_start: — strict > keeps the earliest-found span on ties.
• s[best_start : best_end + 1] — +1 since slicing excludes the stop but best_end is inclusive.
• if not s: return "" — guards the empty-string edge case up front.

How to Recognize This Pattern