Longest Palindromic Substring

You are given a string S of length N. Your task is to find the longest palindromic substring of S using dynamic programming. A palindrome is a string that reads the same backward as forward. The dynamic programming recurrence used to compute whether a substring S[i...j] is a palindrome is given by:

\( dp[i][j] = \begin{cases} 1 & \text{if } i = j, \\ 1 & \text{if } S[i] = S[j] \text{ and } j-i=1, \\ 1 & \text{if } S[i] = S[j] \text{ and } dp[i+1][j-1] = 1, \\ 0 & \text{otherwise.} \end{cases} \)

If there are multiple valid longest palindromic substrings, output the one that is obtained by the latest update in the dynamic programming table.

For example:

• For S = "babad", one valid answer is "aba".
• For S = "cbbdadaedfse", the answer is "ada".
• For S = "abc", the answer is any single character (e.g. "a").

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains an integer \( N \) which denotes the length of the string \( S \).
2. The second line contains the string \( S \) itself.

outputFormat

Output via standard output (stdout) the longest palindromic substring found in \( S \). If there are multiple longest palindromic substrings, output the one that is identified according to the dynamic programming update order.

5
babad

aba