Longest Palindromic Substring

Given a string s, your task is to find the longest palindromic substring in s. A palindrome is a string that reads the same backward as forward. If there are multiple answers, return the one that appears first in the string.

Note: A single character is considered a palindrome. The solution must handle even and odd length palindromes correctly.

Hint: You can expand around each center to check for palindromes.

The formula for checking a palindrome centered at index i (for odd length) or between i-1 and i (for even length) can be expressed as:

\( s[low] = s[high] \) for low and high expanding outward.

inputFormat

The input consists of a single line containing a non-empty string s (with only ASCII characters).

outputFormat

Output the longest palindromic substring of s to stdout.

babad

bab