Longest Palindromic Substring

Given a string s, find and return its longest palindromic substring. If there exist multiple substrings of the same maximum length, return the first one encountered (i.e., the one with the smallest starting index). If the input string is empty, output an empty string.

A palindrome is defined as a sequence that reads the same backward as forward. Formally, a substring \(s[i \ldots j]\) is a palindrome if \(s[i]=s[j]\) for all valid indices where \(0 \leq i \leq j < n\).

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output the longest palindromic substring found in s to stdout.

babad

bab