Longest Palindromic Substring

Return the longest continuous palindrome in a string.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Longest Palindromic Substring: Every odd or even palindrome is discovered by expanding its unique center; update the saved range only when an expansion is strictly longer.

Input and goalReturn the longest continuous palindrome in a string.

Initialize best rangeFor text babad, best_left = best_right = 0, so the initial saved palindrome is b.

best [0,0]b0a1b2a3d4

inputbabadbestRange[0,0] -> b

Recognize it

The answer is a contiguous palindrome, whose symmetry guarantees one unique odd character center or even gap center.

Keep true

Within expand(left,right), text[left:right+1] is palindromic before the pointers move outward. After each completed center, the saved range is the longest palindrome seen at any processed center.

Reuse it

When validity is symmetric around a center, enumerate both center types and expand until the invariant breaks; change only the aggregation to find a longest value, count all values, or validate radii.

Pattern: Expand from every center.

Simple idea: Every palindrome has one center character or a gap between two center characters. Expand both forms at every position and save the longest range.

def longest_palindrome(text: str) -> str:
   best_left = best_right = 0

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

   for middle in range(len(text)):
      expand(middle, middle)
      expand(middle, middle + 1)
   return text[best_left : best_right + 1]

Cost: $O(n^2)$ time and $O(1)$ space.