Longest Palindromic Substring

Given a string s, your task is to find the longest contiguous substring that is a palindrome. A palindrome is a sequence of characters that reads the same backwards as forwards. For example, in the string "babad", one correct answer is "bab", although "aba" is also acceptable. In case of multiple answers with the same length, you may output any one of them.

Note: The input string may be empty, and in that case, the output should also be an empty string.

The expected solution should use an optimal approach, such as dynamic programming.

inputFormat

The input consists of a single line containing a string s. The string can include alphabets, digits, and special characters. Leading and trailing whitespaces should be trimmed.

outputFormat

Output the longest palindromic substring found in the input string. If there are multiple valid answers, output any one of them.

a

a