Longest Palindromic Substring

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

A palindrome is a string that reads the same backwards as forwards. If there are multiple palindromic substrings of maximum length, output the one that appears first in s.

Note: A single character is by default a palindrome.

Example:

• Input: babad. Output: bab (as aba is also acceptable, but your solution should choose one that appears first).
• Input: cbbd. Output: bb.

The center expansion approach is often used in solving such problems with a time complexity of \(O(n^2)\), where \(n\) is the length of the string.

inputFormat

The input consists of a single line containing the string s. The string may include both uppercase and lowercase letters and can be empty.

outputFormat

Output the longest palindromic substring of s using standard output. If there are multiple answers, output the one that appears first.

babad

bab