5 - Longest Palindromic Substring

Difficulty: Medium | Pattern: Expand Around Center | Company tags: Amazon, Google, Microsoft, Facebook, Bloomberg

Problem Statement

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

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

Key Insight

A palindrome expands symmetrically from its center. There are 2n - 1 possible centers: each character (for odd-length palindromes) and each gap between characters (for even-length palindromes). Expand around each center to find the longest palindrome.

Approach 1: Expand Around Center — O(n²) time, O(1) space

def longestPalindrome(s: str) -> str:
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # When loop exits, s[left+1:right] is the palindrome
        return s[left+1:right]
    
    best = ""
    for i in range(len(s)):
        odd = expand(i, i)       # center at one character
        even = expand(i, i+1)    # center between two characters
        if len(odd) > len(best):
            best = odd
        if len(even) > len(best):
            best = even
    
    return best

Dry Run

s = "babad"

Center	Expansion	Palindrome
i=0, odd	expand(0,0): "b"	"b"
i=1, odd	expand(1,1): s[0]='b'==s[2]='b' → "bab"	"bab"
i=1, even	expand(1,2): s[1]='a'≠s[2]='b'	"a" → "" (length 0 slice)
i=2, odd	expand(2,2): "abad" → s[1]='a'==s[3]='a' → "aba"	"aba"
i=3, odd	expand(3,3): s[2]='b'≠s[4]='d'	"a"

Best palindrome: "bab" (length 3) ✓

Approach 2: Manacher's Algorithm — O(n) time, O(n) space

Manacher's algorithm finds all palindrome lengths in O(n) using the palindrome-within-palindrome property. It's complex but optimal.

For most interviews, Expand Around Center is sufficient and much easier to explain.

Approach 3: DP — O(n²) time, O(n²) space

def longestPalindrome(s: str) -> str:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    
    # All single chars are palindromes
    for i in range(n):
        dp[i][i] = True
    
    # Check length 2
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start, max_len = i, 2
    
    # Check lengths 3 to n
    for length in range(3, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                if length > max_len:
                    start, max_len = i, length
    
    return s[start:start+max_len]

Complexity Comparison

Approach	Time	Space	Recommended?
Expand around center	O(n²)	O(1)	Yes — simple and space-efficient
DP	O(n²)	O(n²)	No — extra space for same time
Manacher's	O(n)	O(n)	Advanced — hard to implement under time pressure