Longest Palindromic Substring

Given a string s consisting of lowercase alphabetic characters (and possibly spaces), find the longest contiguous substring that is a palindrome.

A palindrome is defined as a sequence of characters that reads the same backward as forward. Note that in this problem, you are only required to find a contiguous substring, and the palindrome check is case-sensitive. Formally, a substring s[i...j] is a palindrome if and only if \(s[i] = s[j]\) and the substring s[i+1...j-1] is also a palindrome. The simplest cases are strings of length 0 or 1, which are trivially palindromic.

Your program should read the input from standard input (STDIN) and output the longest palindromic substring to standard output (STDOUT). In case there are multiple answers, output the one found by the algorithm described below.

Hint: One effective approach to solve this problem is the expand around center technique. For each character (or pair of characters) in the string, expand outward while the characters on both sides are equal.

For further reference, the expansion can be formalized as follows: if we assume i is the center, then expand while \(s[i - k] = s[i + k]\) for \(k \geq 0\) and within the bounds of the string.

inputFormat

The input consists of a single line containing a string s. The string will contain only lowercase English letters and spaces. It can be an empty string as well.

Input is provided via standard input (STDIN).

outputFormat

Output the longest palindromic substring found in s on a single line. The output should be sent to standard output (STDOUT).

babad

bab