Longest Palindromic Substring

Solving tips

Prefer expand-around-center over the 2-D table: every palindrome has one of 2n-1 centers, giving O(n^2) time and O(1) space.
Expand from both (i,i) for odd lengths and (i,i+1) for even lengths, or you miss palindromes like 'bb'.
The palindrome recurrence is s[i]==s[j] and inside s[i+1..j-1] is a palindrome (or length <= 1).
After expansion the last matching window is [left+1, right-1]; return the substring, not its length. Manacher reaches O(n) if needed.

Problem

Given a string s, return the longest contiguous substring of s that reads the same forwards and backwards. If several are tied for longest, returning any one of them is fine.

Examples

s = "babad" → "bab" — "aba" is an equally valid answer (both length 3).
s = "cbbd" → "bb" — the only even-length palindrome beats every single character.
s = "a" → "a" — a single character is a palindrome of length 1.

Constraints

1 <= s.length <= 1000
s consists of digits and English letters.

Think about it first

Hint 1

Brute force checks every substring for the palindrome property — O(n²) substrings, O(n) to check each, O(n³) total. Too slow, but it frames the sub-question: "is s[i..j] a palindrome?"

Hint 2

That sub-question has beautiful recursive structure: s[i..j] is a palindrome iff s[i] == s[j] AND the inside s[i+1..j-1] is a palindrome (or is length ≤ 1). That's a 2-D boolean DP over (i, j).

Hint 3

Or flip it around: every palindrome has a center. There are 2n-1 centers (each character, and each gap between characters). Expand outward from each center while the two ends match, and track the longest span. O(n²) time, O(1) space, no table.

TL;DR

Expand around each of the 2n-1 centers — O(n²) time, O(1) space. A 2-D DP gives the same time in O(n²) space; Manacher’s algorithm reaches O(n).

Approach 1 — Brute force

Check every substring; keep the longest palindrome. A string is a palindrome iff it equals its reverse.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        best = ""
        for i in range(n):
            for j in range(i, n):
                sub = s[i:j + 1]
                if sub == sub[::-1] and len(sub) > len(best):
                    best = sub
        return best

Complexity: O(n²) substrings × O(n) reverse-compare = O(n³) time. At n = 1000 that’s a billion operations — the constraints kill it.

Approach 2 — 2-D DP table (top-down / bottom-up)

The insight: define dp[i][j] = True iff s[i..j] is a palindrome. This is genuine 1-D-flavored DP on substring length: a length-L palindrome depends only on the length-(L-2) one inside it.

Recurrence: dp[i][j] = (s[i] == s[j]) and (j - i < 2 or dp[i+1][j-1]).

Because dp[i][j] reads dp[i+1][j-1], we fill by increasing substring length so the inner span is already known.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        start, length = 0, 1
        for i in range(n):
            dp[i][i] = True                     # length 1
        for j in range(n):
            for i in range(j):
                if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    if j - i + 1 > length:
                        start, length = i, j - i + 1
        return s[start:start + length]

Walkthrough (s = "cbbd"): diagonal (length 1) all True. For j=2, i=1: s[1]==s[2] ('b'=='b') and j-i < 2, so dp[1][2]=True, span length 2 → start=1, length=2. No length-3/4 palindrome forms. Return s[1:3] = "bb". ✓

Complexity: O(n²) time, O(n²) space.

Approach 3 — Expand around center (space-optimized)

The insight: a palindrome is fully determined by its center, and there are only 2n - 1 centers — n single characters (odd length) and n - 1 gaps between characters (even length). Expand each outward while the ends match; no table needed.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        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   # last matching bounds

        for i in range(len(s)):
            l1, r1 = expand(i, i)        # odd-length center
            if r1 - l1 > end - start:
                start, end = l1, r1
            l2, r2 = expand(i, i + 1)    # even-length center
            if r2 - l2 > end - start:
                start, end = l2, r2
        return s[start:end + 1]

Walkthrough (s = "babad"): center i=1 ('a'), odd expansion matches s[0]==s[2] ('b'=='b') then stops → span [0,2] = "bab", length 3, recorded. No later center beats length 3. Return "bab". ✓

Complexity: O(n²) time (each of 2n-1 centers expands up to O(n)), O(1) extra space.

Approach 4 — Manacher’s algorithm (O(n))

The insight: Manacher’s algorithm computes, in linear time, the palindrome radius at every center by reusing mirror information — when you’re inside a known palindrome, the radius at a position is at least that of its mirror, so you skip re-checking. Transform s by inserting a separator (e.g. #) between every character so odd and even cases unify.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        t = "#" + "#".join(s) + "#"
        n = len(t)
        radius = [0] * n
        center = right = 0
        best_len = best_center = 0
        for i in range(n):
            if i < right:
                radius[i] = min(right - i, radius[2 * center - i])
            while (i - radius[i] - 1 >= 0 and i + radius[i] + 1 < n
                   and t[i - radius[i] - 1] == t[i + radius[i] + 1]):
                radius[i] += 1
            if i + radius[i] > right:
                center, right = i, i + radius[i]
            if radius[i] > best_len:
                best_len, best_center = radius[i], i
        start = (best_center - best_len) // 2
        return s[start:start + best_len]

Complexity: O(n) time, O(n) space — the theoretical best, though expand-around-center is the more commonly expected interview answer.

Common pitfalls

Handling only odd-length centers and missing even palindromes like "bb" — you must expand from both (i, i) and (i, i+1).
In the 2-D DP, filling dp in plain row-major order reads dp[i+1][j-1] before it’s computed; iterate by increasing length (or by j outer, i inner as above).
Off-by-one when converting expand bounds to a slice: after the loop the last matching window is [left+1, right-1].
Returning the length instead of the substring — the problem wants the substring itself.

Pattern takeaway

“Is s[i..j] a palindrome?” has the recurrence s[i]==s[j] and inside-is-palindrome, which powers a whole family of palindrome-DP problems. When a DP over substrings only ever peels one character off each end, the center-expansion reformulation often erases the O(n²) table down to O(1) space — reach for it whenever the structure is “grows symmetrically from a middle.”