Longest Palindromic Substring

Interview Prep

HardDynamic Programmingstringsdp

The problem

Given a string s, return the longest substring that is a palindrome. If multiple substrings tie, return any of them.

Three solutions, three complexities

The interview standard is the O(n²) center-expansion method — clean, easy to derive on the spot. The O(n²) DP gives the same complexity but is more memory-heavy and worth knowing because it generalizes to related problems. Manacher's algorithm hits O(n) and is one of the most beautiful string algorithms; senior interviewers occasionally ask about it.

Pattern: every palindrome has a center

There are 2n − 1 possible centers — n odd-length centers (each character) and n − 1 even-length centers (each gap between adjacent characters). From every center, expand outward while the characters at the new boundary match. Track the longest seen. O(n²) in the worst case (a string of identical characters).

Center expansion

def longest_palindrome(s: str) -> str:
    """Center expansion: try every possible center (single char and gap-between-chars)."""
    if not s: return ""
    best_lo, best_hi = 0, 0
    n = len(s)
    for c in range(n):
        # Odd-length: center at c
        lo, hi = c, c
        while lo >= 0 and hi < n and s[lo] == s[hi]:
            lo -= 1; hi += 1
        if (hi - 1) - (lo + 1) > best_hi - best_lo:
            best_lo, best_hi = lo + 1, hi - 1
        # Even-length: center between c and c+1
        lo, hi = c, c + 1
        while lo >= 0 and hi < n and s[lo] == s[hi]:
            lo -= 1; hi += 1
        if (hi - 1) - (lo + 1) > best_hi - best_lo:
            best_lo, best_hi = lo + 1, hi - 1
    return s[best_lo:best_hi + 1]

Trace

s = "babad"

Center c=0 (odd):  "b"     - len 1
Center c=0 (even): "ba"    - no, mismatch immediately
Center c=1 (odd):  "bab"   - len 3, expand: l=0,r=2 ok ('b'=='b'); l=-1 stop
Center c=1 (even): "ab"    - mismatch
Center c=2 (odd):  "aba"   - len 3, expand: l=1,r=3 ok ('a'=='a'); l=0,r=4 mismatch ('b'!='d')
Center c=2 (even): "ab"    - mismatch
Center c=3 (odd):  "d"     - len 1
Center c=3 (even): "ad"    - mismatch
Center c=4 (odd):  "d"     - len 1

Best is len 3.  "bab" found first, "aba" also valid (problem allows either).

return "bab"

Alternative: 2D DP

dp[i][j] = True iff s[i..j] is a palindrome. Recurrence: dp[i][j] = (s[i] == s[j]) ∧ (length ≤ 2 or dp[i+1][j−1]). Fill by increasing length so dependencies are ready. Same complexity, more memory, but generalizes to "count palindromic substrings", "palindrome partitioning", and others. 

def longest_palindrome_dp(s: str) -> str:
    """O(n^2) DP. dp[i][j] = is s[i..j] a palindrome?  Fill by increasing length."""
    n = len(s)
    if n == 0: return ""
    dp = [[False] * n for _ in range(n)]
    best_lo, best_len = 0, 1
    for i in range(n): dp[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                if length > best_len:
                    best_lo, best_len = i, length
    return s[best_lo:best_lo + best_len]

Manacher in O(n)

The famous trick: insert separators between every character so every palindrome is odd-length under the new representation. Then sweep left-to-right, maintaining the rightmost palindrome seen so far, and reuse its mirror's reach as a free initial lower bound at each new center. The amortised analysis is the same as the Z-function — the "right boundary" only moves forward. 

def longest_palindrome_manacher(s: str) -> str:
    """O(n) Manacher.  Transform 'abc' -> '^#a#b#c#$' to unify even/odd cases."""
    t = '^#' + '#'.join(s) + '#$'
    n = len(t)
    p = [0] * n
    center = right = 0
    for i in range(1, n - 1):
        # Mirror within the current "right" boundary, if applicable
        mirror = 2 * center - i
        if i < right:
            p[i] = min(right - i, p[mirror])
        # Try to extend the palindrome centered at i
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        # Update the rightmost palindrome
        if i + p[i] > right:
            center, right = i, i + p[i]
    # Recover the original substring
    max_i = max(range(n), key=lambda i: p[i])
    radius = p[max_i]
    start = (max_i - radius) // 2
    return s[start:start + radius]

Complexity

Variations worth knowing