Problem 64 · Strings & Tries

Longest Palindromic Substring

MediumClassic DSA & systems

01Problem

Return the longest palindromic substring of s.

02Key insight

Every palindrome has a center: 2n-1 centers (characters and gaps). Expanding around each is O(n^2) time, O(1) space; Manacher's reaches O(n) if asked.

03Solution

solution.pypython15 lines

def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    best_lo, best_hi = 0, 0  # inclusive bounds

    def expand(lo: int, hi: int) -> tuple[int, int]:
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo, hi = lo - 1, hi + 1
        return lo + 1, hi - 1

    for i in range(len(s)):
        for lo, hi in (expand(i, i), expand(i, i + 1)):
            if hi - lo > best_hi - best_lo:
                best_lo, best_hi = lo, hi
    return s[best_lo:best_hi + 1]

Try it first.

TimeO(n^2)

SpaceO(1)

tests.py · 5 passing

tests.pypython5 lines

assert longest_palindrome("babad") in ("bab", "aba")
assert longest_palindrome("cbbd") == "bb"
assert longest_palindrome("a") == "a"
assert longest_palindrome("") == ""
assert longest_palindrome("forgeeksskeegfor") == "geeksskeeg"

04Staff-level follow-up

Need O(n)? Manacher's algorithm reuses mirror radii inside the rightmost known palindrome; or suffix automaton / hashing + binary search for O(n log n).