Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. A palindrome is a string that reads the same backward as forward. In other words, find a substring p of s such that p = p^R and the length of p is maximized.

If there are multiple answers, you may output any one of them.

Note: A substring is a contiguous sequence of characters within a string. The approach frequently used for this problem is to expand around each character (and the gap between two characters) to check for palindromes. Specifically, for a given index i, you check for palindromes centered at i (for odd-length palindromes) and centered between i and i+1 (for even-length palindromes).

In mathematical terms, we define the expansion as follows: Given a center (or centers) l and r, expand while s[l] = s[r] until the condition fails. The palindrome found is s[l+1...r-1].

inputFormat

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

outputFormat

Output the longest palindromic substring of s. If there are multiple valid answers, output any one of them.

babad

bab