Longest Palindromic Substring

Given a string s, find and return its longest palindromic substring.

A substring is a contiguous sequence of characters in a string, and a palindrome is a string that reads the same forwards and backwards. The problem can be solved using dynamic programming by defining a state: \(dp[i][j]\) is true if the substring \(s[i\ldots j]\) is a palindrome. The recurrence relation is given by:

\[ dp[i][j] = \begin{cases} true & \text{if } i = j, \\ (s[i] = s[j]) & \text{if } j = i+1, \\ dp[i+1][j-1] \land (s[i] = s[j]) & \text{if } j > i+1. \end{cases} \]

Your task is to implement this logic and output the longest palindromic substring found. In the event that there exist multiple palindromic substrings of maximum length, output the one that appears first in the string.

inputFormat

The input consists of a single line containing a non-empty string s. The string consists of letters and may also contain other printable characters.

outputFormat

Output a single line containing the longest palindromic substring of s.

babad

aba