Longest Palindromic Substring

Intuition

Every palindrome has a center: for odd lengths it is a single character, and for even lengths it is the seam between two characters. If we fix that center and push two pointers apart, the substring stays a palindrome exactly while the characters on either side keep matching. By trying all 2n - 1 possible centers and expanding each one, we are guaranteed to discover the longest palindrome without checking every substring explicitly.

Algorithm walkthrough

1. 1Track the best starting index and best length found so far, initialized to the first character.
2. 2For each position in the string, consider two centers: the character itself (odd length) and the gap just after it (even length).
3. 3From each center, move a left pointer down and a right pointer up while both stay in bounds and the characters they point to are equal.
4. 4Whenever an expansion yields a span longer than the current best, record its start index and length.
5. 5After examining every center, return the substring described by the best start index and length.

Implementation

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        best_start, best_len = 0, 1

        def expand(left: int, right: int) -> None:
            nonlocal best_start, best_len
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > best_len:
                    best_len = right - left + 1
                    best_start = left
                left -= 1
                right += 1

        for center in range(len(s)):
            expand(center, center)
            expand(center, center + 1)
        return s[best_start:best_start + best_len]