Longest Palindromic Substring

Given a string \(s\), find and return the longest contiguous palindromic substring of \(s\). A palindrome is a string that reads the same forwards and backwards. If there are multiple palindromic substrings of the same maximum length, return the one that appears first in \(s\).

The optimal solution should be efficient enough to handle moderately long strings. One recommended approach is to expand around each possible center of the palindrome, considering both odd-length and even-length centers.

The core idea is to iterate over the string, treating each index as the center of a potential palindrome, and then expand outwards while the characters on both sides are the same.

Mathematically, if a substring \(s[i \ldots j]\) is a palindrome then:

\[ \text{if } s[i]=s[j] \text{ and } s[i+1\ldots j-1] \text{ is a palindrome, then } s[i\ldots j] \text{ is a palindrome.} \]

inputFormat

The input consists of a single line containing the string \(s\). The string may include any printable characters.

outputFormat

Output the longest palindromic substring found in \(s\). Print the result to standard output.

## sample

babad

bab