Longest Palindromic Substring

Problem

Given a string, return its longest palindromic substring.

Approach

Every palindrome is symmetric around a centre. That centre is either a single character, for odd lengths, or the gap between two characters, for even lengths.

For each of the 2n - 1 possible centres, expand outward while the characters on both sides match, and keep the widest result.

A dynamic programming table of which substrings are palindromes gives the same O(n²) time but needs O(n²) memory, so expanding around centres is the leaner choice.

Solution

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

        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
            return left + 1, right - 1

        for i in range(len(s)):
            for left, right in (expand(i, i), expand(i, i + 1)):
                if right - left > end - start:
                    start, end = left, right

        return s[start:end + 1]

Complexity

• Time: O(n²): up to n expansions from each centre.
• Space: O(1).

Edge cases

• A single character is its own longest palindrome.
• Even-length palindromes such as abba need the between-characters centre.
• A string with no repeated neighbours returns its first character.