Longest Palindromic Substring

Problem Return the longest contiguous palindromic substring of s.

Input / Output

• Input: string s. Output: the longest palindromic substring (any one if tied).

Constraints

• |s| up to 1000 → O(n^2)/O(1) expand-around-center expected; know Manacher exists for O(n).

Example

• "babad" → "bab" or "aba"; "cbbd" → "bb".

Expected approach

• Expand around all 2n−1 centers (each character and each gap for even lengths), tracking the best span — O(n^2) time, O(1) space; the even-center case is the common miss. DP table isPal[i][j] is O(n^2) space for the same time — say why expansion wins. Mention Manacher's for the O(n) flex. Contrast with longest palindromic SUBSEQUENCE (different problem, interval DP) — a favorite probe.