Longest Palindromic Substring

Given a string S consisting of lowercase English letters, your task is to find the longest palindromic substring within S. A palindrome is a string that reads the same backwards as forwards.

If there are multiple longest palindromic substrings of equal length, return the one that appears first in S.

Note: A substring is a contiguous sequence of characters within a string.

You may find the following mathematical representation useful: A string \( S = s_1s_2 \cdots s_n \) has a palindromic substring \( S[i...j] \) if \( s_i = s_j, s_{i+1} = s_{j-1}, \ldots \).

inputFormat

The input consists of a single line containing the string S. The string will only contain lowercase English letters and may be empty.

outputFormat

Output the longest palindromic substring found in the input string. If there are multiple, output the one that appears first.

babad

aba