Longest Palindromic Substring

Given a string s, your task is to find and print its longest palindromic substring. A palindrome is a string that reads the same backward as forward. In case there are more than one longest palindromic substrings, you can output the one that appears first in the string.

The solution should be efficient enough to handle strings of moderate length. The algorithm typically expands around potential centers to find palindromic substrings. The underlying idea is to consider every character (and the gap between characters) as a center and expand outward as long as the characters are equal.

Note: If the input string is empty, print an empty string.

inputFormat

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

The string can contain any characters and may be empty.

outputFormat

Output the longest palindromic substring found in s on a single line.

babad

bab