Longest Palindromic Substring

Problem

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

A string is a palindrome when it reads the same backward as forward.

Input: String s. Output: Longest palindromic substring (any valid choice if ties).

Input: s = "babad" → Output: "bab" (or "aba")

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

Expand Around Center — Each character (and each pair) is a potential palindrome center. Expand outward while characters match. Track longest. Time: O(n²), Space: O(1). Handles both odd-length (center is single char) and even-length (center is gap between two chars).
DP — dp[i][j] = true if s[i..j] is palindrome. Transition: dp[i][j] = (s[i]==s[j]) && (j-i<2 || dp[i+1][j-1]). Time/Space: O(n²).
Manacher's algorithm — O(n) but rarely needed in interviews.

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

A string is a palindrome when it reads the same backward as forward.

Input: String s. Output: Longest palindromic substring (any valid choice if ties).

Input: s = "babad" → Output: "bab" (or "aba")

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

Expand Around Center — Each character (and each pair) is a potential palindrome center. Expand outward while characters match. Track longest. Time: O(n²), Space: O(1). Handles both odd-length (center is single char) and even-length (center is gap between two chars).
DP — dp[i][j] = true if s[i..j] is palindrome. Transition: dp[i][j] = (s[i]==s[j]) && (j-i<2 || dp[i+1][j-1]). Time/Space: O(n²).
Manacher's algorithm — O(n) but rarely needed in interviews.