Longest Palindromic Substring

Given a string \( s \) consisting of lowercase English letters, you are required to find the longest palindromic substring within \( s \). A palindrome is a string that reads the same backward as forward. If there exist multiple longest palindromic substrings, output the one that occurs first (i.e. has the smallest starting index).

Example 1: For input babad, the answer is bab.

Example 2: For input cbbd, the answer is bb.

The solution is expected to run efficiently even for larger inputs. One common approach is to use the expand-around-center method to check all potential palindromic centers in \( O(n^2) \) time in the worst-case scenario.

inputFormat

The input consists of a single line. This line contains the string \( s \) made up of lowercase English letters. The string may be empty.

outputFormat

Output the longest palindromic substring found in \( s \). If there are multiple answers, output the one with the smallest starting index.

babad

bab