Longest Palindromic Substring

Given a string s, your task is to find the longest palindromic substring within s. A palindromic substring is a sequence of characters that reads the same forwards and backwards. If there are multiple substrings that are palindromic and share the maximum length, return the one that appears first in the string.

Mathematically, a palindrome satisfies the condition $$s[i] = s[n-i+1]$$ for every valid index inside the substring (expressed in \(\LaTeX\) format). Input is provided via standard input and the result should be output to standard output.

inputFormat

The input consists of a single line containing a non-empty string s made up of uppercase and lowercase English letters.

outputFormat

Output the longest palindromic substring in s. If there are several with the same length, output the one that occurs first.

babad

aba