Longest Palindromic Substring

Given a string s, return the longest substring of s that is a palindrome.

A palindrome is a string that reads the same forward and backward.

If there are multiple palindromic substrings that have the same length, return any one of them.

Both "aba" and "bab" are valid answers.

Approach

Expand around every possible center. For each index, expand for odd-length and even-length palindromes and track the longest span. Return the substring defined by the best span.

Why It Works

Every palindrome is centered at either a character (odd length) or between two characters (even length). Expanding around all centers explores every palindrome and keeps the maximum length found.

Complexity

• Time: O(n^2)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        start, end = 0, 0

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

        for i in range(len(s)):
            l1, r1 = expand(i, i)
            l2, r2 = expand(i, i + 1)
            if r1 - l1 > end - start:
                start, end = l1, r1
            if r2 - l2 > end - start:
                start, end = l2, r2
        return s[start:end + 1]