Longest Palindromic Substring

Given a string s, your task is to find the longest palindromic substring within s. A palindrome is a string that reads the same backward as forward. Formally, a string \( s \) of length \( n \) is a palindrome if \( s[i] = s[n-i+1] \) for all \( 1 \leq i \leq n \) (using 1-indexing). If there are multiple palindromic substrings with the same maximum length, return the one that appears first in the string.

Example:

Input: babad
Output: bab

Note: In the sample above, "aba" is also a valid answer, but since the requirement is to output the first encountered one, "bab" is returned.

inputFormat

The input consists of a single line containing the string s (with length at least 1 and at most 1000) provided via standard input.

outputFormat

Output the longest palindromic substring of the given string. If there is more than one solution, output the one that appears first.

babad

bab