Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. A palindrome is a string that reads the same forward and backward. If there are multiple substrings with the maximum length, you may output any one of them. If s is empty, output an empty string.

The approach should typically involve expanding around each character (and between two characters) to check for palindromic substrings. Mathematically, the problem can be described as finding a substring s[i...j] such that for all k with 0 \leq k \leq j-i, it holds that \[ s[i+k] = s[j-k], \] with maximum length j - i + 1.

inputFormat

The input consists of a single line containing the string s. The string may be empty and contains only ASCII characters.

outputFormat

Output the longest palindromic substring in s. If there are multiple correct answers, output any one of them. If s is empty, output an empty string.

babad

aba