Longest Palindromic Substring

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

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.

def longestPalindrome(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 is roughly a billion operations, too slow for the constraints.

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

Define dp[i][j] = True iff s[i..j] is a palindrome. The dependency runs on substring length: a length-L palindrome depends only on the length-(L-2) substring 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], fill by increasing substring length so the inner span is already known.

flowchart LR
  A["s[i] == s[j]"] --> C["dp[i][j]"]
  B["dp[i+1][j-1]<br/>(inner substring)"] --> C

def longestPalindrome(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"): the diagonal (length 1) is 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, giving start=1, length=2. No length-3 or length-4 palindrome forms. Return s[1:3] = "bb".

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

Approach 3 — Expand around center (space-optimized)

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.

def longestPalindrome(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, giving span [0,2] = "bab", length 3. 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))

Manacher’s algorithm computes the palindrome radius at every center in linear time by reusing mirror information: inside a known palindrome, the radius at a position is at least that of its mirror, so those checks are skipped. Transform s by inserting a separator (e.g. #) between every character so the odd and even cases unify.

def longestPalindrome(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 underlies a family of palindrome-DP problems. When a DP over substrings only peels one character off each end, the center-expansion reformulation often reduces the O(n²) table to O(1) space. It applies whenever the structure grows symmetrically from a middle.