Skip to content

5. Longest Palindromic Substring

On LeetCode ->

Reformulated question

Given a string s, return any longest contiguous substring that is a palindrome.

Compact example:

s = "babad" -> "bab"   # "aba" is also valid

Key trick

Expand around every possible center.

  • Every palindrome is centered either on:
    • one character, like "aba"
    • the gap between two characters, like "abba"
  • For each center, grow left and right while characters match.
  • Keep the longest range found.

Trap

Common mistakes:

  • Forgetting even-length palindromes like "bb".
  • Returning a subsequence instead of a substring.
  • Re-slicing strings inside the inner loop too much.
  • Off-by-one errors on bounds.
  • Assuming the answer is unique for cases like "babad".

Why this question is interesting

It looks like DP or brute force, but the clean interview solution is center expansion.

  • Brute force is \(O(n^3)\).
  • Center expansion is simple and \(O(n^2)\) with \(O(1)\) extra space.
  • It tests string indexing, edge cases, and clear reasoning.

Solve the problem with idiomatic python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Best palindrome boundaries: s[best_l:best_r + 1]
        best_l = 0
        best_r = 0

        def expand(left: int, right: int) -> tuple[int, int]:
            # Grow while s[left:right+1] stays palindrome.
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1

            # Loop exits one step after valid palindrome.
            return left + 1, right - 1

        for i in range(len(s)):
            # Odd-length palindrome centered at i.
            l1, r1 = expand(i, i)

            # Even-length palindrome centered between i and i + 1.
            l2, r2 = expand(i, i + 1)

            if r1 - l1 > best_r - best_l:
                best_l, best_r = l1, r1

            if r2 - l2 > best_r - best_l:
                best_l, best_r = l2, r2

        return s[best_l:best_r + 1]

Pytest test

import pytest


@pytest.mark.parametrize(
    ("s", "expected_set"),
    [
        ("a", {"a"}),
        ("ac", {"a", "c"}),
        ("bb", {"bb"}),
        ("babad", {"bab", "aba"}),
        ("cbbd", {"bb"}),
        ("racecar", {"racecar"}),
        ("aaaa", {"aaaa"}),
        ("bananas", {"anana"}),
        ("abcda", {"a", "b", "c", "d"}),
    ],
)
def test_longestPalindrome(s, expected_set):
    assert Solution().longestPalindrome(s) in expected_set

Comment my solution

Your solution is correct and interview-valid.

Good parts:

  • Uses the right idea: expand around center.
  • Handles both odd and even palindromes.
  • Time/space complexity is right: \(O(n^2)\) and \(O(1)\) extra space.

What I would improve:

  • Track indices instead of storing sliced substrings during expansion.
  • len(ch) is always 1, so that line is unnecessary.
  • Repeating the same expansion logic twice is a bit noisy; a helper makes it cleaner.
  • Slicing inside the loop creates extra strings repeatedly.

A small fix in your style would be to update only boundaries during expansion, then slice once at the end.

## Solution
class Solution:
    def longestPalindrome(self, s: str) -> str:
        best_palin = ""
        # we grow sliding window around mid until the string in the
        # sliding window no longer is a palindrome
        for mid, ch in enumerate(s):
            best_palin = best_palin if len(ch) < len(best_palin) else ch

            # even palindrome centered in mid
            left, right = mid - 1, mid
            while -1 < left and right < len(s):
                if s[left] != s[right]:
                    break
                best_palin = best_palin if right - left + 1 < len(best_palin) else s[left:right + 1]
                left -= 1
                right += 1

            # odd palindrome centered in mid
            left, right = mid - 1, mid + 1
            while -1 < left and right < len(s):
                if s[left] != s[right]:
                    break
                best_palin = best_palin if right - left + 1 < len(best_palin) else s[left:right + 1]
                left -= 1
                right += 1
        return best_palin

Solution().longestPalindrome("babad") # 'aba'