Longest Palindromic Substring

Problem Given a string s, find the longest substring of s that is a palindrome.

Input / Output

• Input: string s.
• Output: the longest palindromic substring; if several tie in length, any one is acceptable.

Constraints

• 1 <= |s| <= 1000 for the O(n^2) solution to pass; matching is case-sensitive.
• Substring, not subsequence — the characters must be contiguous.
• Every single character is trivially a palindrome, so the answer is never empty.

Example

• "babad" → "bab" (or "aba" — both length 3).
• "cbbd" → "bb" — the even-length case a centers-only-at-characters loop would miss.
• "ac" → "a" (or "c"); no multi-character palindrome exists.