Longest Palindromic Substring

Given a string s, find the longest palindromic substring present in it. A string is said to be a palindrome if it reads the same forward and backward. In mathematical terms, a string \(s\) is palindromic if \(s = s^R\), where \(s^R\) denotes the reverse of \(s\).

If there are multiple answers, output the one that appears first in s. For example:

• Input: babad → Output: aba (or bab)
• Input: cbbd → Output: bb

inputFormat

The input consists of a single line containing the string s. The string may contain spaces and its length does not exceed 1000 characters.

outputFormat

Output the longest palindromic substring of s on a single line.

babad

aba