Shortest Palindromic Substring

Given a string s, your task is to find the shortest substring of s that is a palindrome. A palindrome is a string that reads the same backwards as forwards. If there are multiple palindromic substrings with the same minimal length, output the one that appears first in the string.

If the input string is empty, output an empty string.

The problem can be mathematically formalized as follows:

Find the smallest l such that there exists an index i with
\(s[i:i+l] = \text{reverse}(s[i:i+l])\) and output that substring. If multiple such substrings exist, choose the one with the smallest index i.

inputFormat

The input consists of a single string s provided via standard input (stdin). The string may contain any printable characters and can be empty.

outputFormat

Output the shortest palindromic substring of s to standard output (stdout). If there are multiple with the same length, output the first occurring one. For an empty input, print an empty string.

babad

b