Longest Palindromic Substring

Given a non-empty string s consisting of alphanumeric characters, your task is to find the longest substring of s that is a palindrome.

A string is a palindrome if it reads the same backward as forward. For example, the string racecar is a palindrome since \[ racecar = r \; a \; c \; e \; c \; a \; r \] and similarly, anana is a palindrome.

If there are multiple substrings of maximum length, return the one that appears first in the string.

The expected time complexity is roughly \(O(n^2)\) with a center expansion approach.

inputFormat

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

You should read the input from standard input (stdin).

outputFormat

Output a single line, the longest palindromic substring found in s, written to standard output (stdout).

babad

bab