Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Given a string, return the longest contiguous substring that reads the same forward and backward.

The word “substring” is the important constraint. This is not about picking scattered characters. The answer has to be one continuous block inside the original string.

So the real task is:

  • find where the palindrome is centered
  • determine how far it can extend left and right
  • keep the longest one seen

If multiple answers have the same maximum length, returning any one of them is fine.

The key insight

Every palindrome is organized around a center.

  • Odd-length palindromes have a character in the middle, like aba
  • Even-length palindromes have a gap in the middle, like abba

That means the problem can be reframed as:

“For each possible center, how far can the palindrome expand?”

Once that idea clicks, the problem becomes much easier to derive.

How to derive the main solutions

The brute-force version checks every substring and tests whether it is a palindrome.

  • There are O(n^2) substrings
  • Checking each one can take O(n)
  • Total: O(n^3)

That is too slow.

The next improvement is dynamic programming.

If text[left] == text[right], then text[left:right + 1] is a palindrome exactly when the inside part is also a palindrome.

That gives a DP relation:

is_palindrome[left][right] = text[left] == text[right] and is_palindrome[left + 1][right - 1]

This reduces the time to O(n^2), but it still needs O(n^2) extra space.

The best practical interview solution is expand-around-center.

  • Try every possible odd center
  • Try every possible even center
  • Expand while the characters match

This still costs O(n^2) time in the worst case, but it only needs O(1) extra space and is very easy to explain.

The asymptotically optimal solution is Manacher’s algorithm.

It keeps the same center-expansion idea, but it reuses information from previously computed palindromes so the total work becomes linear.

Why Manacher’s algorithm works

The hard part of this problem is that odd-length and even-length palindromes look different.

Manacher solves that first by transforming the string so every palindrome looks like an odd-length palindrome.

For example:

  • original: abba
  • transformed: ^#a#b#b#a#$

The # characters turn every gap into an explicit center, and the sentinels at the ends make the expansion code cleaner.

Now define:

  • radius[i] = how far the palindrome centered at index i extends in the transformed string

The algorithm also tracks:

  • current_center
  • right_boundary, the farthest right edge reached so far by any known palindrome

When a new index falls inside that known boundary, its palindrome has a mirrored index on the other side of the current center. That mirrored radius gives a free lower bound for the new answer.

So instead of expanding from scratch every time, the algorithm:

  1. copies as much radius as it safely can from the mirrored center
  2. expands only beyond the known right boundary
  3. updates the boundary if this palindrome goes farther

That “reuse first, expand only for new territory” idea is why the whole algorithm runs in O(n) time.

Which solution to remember

  • Expand-around-center is the best default interview answer: simple, correct, and uses constant extra space.
  • Manacher’s algorithm is the true optimal runtime solution: O(n) time and O(n) space.

For a summary note like this, it is worth understanding both:

  • center expansion explains the structure of the problem
  • Manacher explains how to remove repeated work

Python solution

The implementation below uses Manacher’s algorithm, with helper methods and comments to keep the logic readable.

class Solution:
    def longestPalindrome(self, text: str) -> str:
        if len(text) < 2:
            return text

        transformed_text = self._transform_text(text)
        palindrome_radii = [0] * len(transformed_text)

        current_center = 0
        right_boundary = 0
        best_center = 0
        best_radius = 0

        for index in range(1, len(transformed_text) - 1):
            mirror_index = 2 * current_center - index

            if index < right_boundary:
                palindrome_radii[index] = min(
                    right_boundary - index,
                    palindrome_radii[mirror_index],
                )

            # Expand only past the part that is already known to be symmetric.
            while (
                transformed_text[index + palindrome_radii[index] + 1]
                == transformed_text[index - palindrome_radii[index] - 1]
            ):
                palindrome_radii[index] += 1

            if index + palindrome_radii[index] > right_boundary:
                current_center = index
                right_boundary = index + palindrome_radii[index]

            if palindrome_radii[index] > best_radius:
                best_center = index
                best_radius = palindrome_radii[index]

        return self._extract_from_original_text(
            original_text=text,
            transformed_center=best_center,
            transformed_radius=best_radius,
        )

    @staticmethod
    def _transform_text(text: str) -> str:
        # Separators unify odd- and even-length palindromes.
        # Sentinels remove boundary checks during expansion.
        return "^#" + "#".join(text) + "#$"

    @staticmethod
    def _extract_from_original_text(
        original_text: str,
        transformed_center: int,
        transformed_radius: int,
    ) -> str:
        start_index = (transformed_center - transformed_radius) // 2
        end_index = start_index + transformed_radius
        return original_text[start_index:end_index]

Closing takeaway

The cleanest mental model is:

the answer is the widest valid expansion around some center.

If the goal is a strong, easy interview answer, use expand-around-center.

If the goal is the asymptotically optimal solution, use Manacher’s algorithm and remember the core trick:

mirror known palindromes, then only spend work on territory that has not been proven yet.