Longest Palindromic Substring

Given a string s, your task is to find the longest palindromic substring in s. A string is said to be a palindrome if it reads the same backward as forward. If there are multiple palindromic substrings of maximum length, you may return any one of them.

The intended solution uses the expand around center technique, which has a time complexity of \(O(n^2)\) and a space complexity of \(O(1)\). This approach iteratively expands potential palindrome centers and tracks the longest palindrome found.

Note: The input string may be empty. In such a case, output an empty string.

inputFormat

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

Example:

aacabdkacaa

outputFormat

Output the longest palindromic substring found in the input string.

Example Output:

aca

## sample

a

a