Longest Palindromic Substring

You are given a string s of length n. Your task is to find the longest palindromic substring of s. A substring is a contiguous sequence of characters within the string and a palindrome is a sequence that reads the same backwards as forwards.

The palindromic substring should be computed using dynamic programming. In particular, you should determine for each substring \(s[i \ldots j]\) whether it is a palindrome, and then return the longest one.

Hint: A single character is always a palindrome. For any substring \(s[i \ldots j]\) with \(j - i + 1 \ge 2\), it is a palindrome if \(s[i] = s[j]\) and \(s[i+1 \ldots j-1]\) is a palindrome.

It is guaranteed that if there are multiple answers, the one found during the usual DP process (checking increasing lengths) will be accepted.

inputFormat

The input consists of a single line containing the string s. The string can contain only ASCII characters. Note, the input is read from standard input (stdin).

outputFormat

Output the longest palindromic substring of s to standard output (stdout). If there is no input string, output an empty string.

babad

bab