Maximum Symmetric Substring

Medium

A symmetric string (also known as a palindrome) is a sequence of characters that reads identically from left to right and from right to left. For example, "radar", "level", and "noon" are all symmetric strings, while "hello" is not. Given a string s consisting of alphanumeric characters, your task is to identify and return the longest contiguous substring within s that is symmetric. A substring is a contiguous sequence of characters within the original string. If multiple symmetric substrings of the same maximum length exist, you may return any one of them as your answer. The input is guaranteed to contain at least one character, and every single character is trivially symmetric.

Example 1

Input

s = "babad"

Output

"bab"

Explanation

The symmetric substrings within "babad" include "b", "a", "bab", and "aba". Both "bab" and "aba" have length 3, which is the maximum. Either answer is acceptable. Here we return "bab".

Example 2

Input

s = "cbbd"

Output

"bb"

Explanation

The longest symmetric substring is "bb" with length 2. Single characters like "c", "b", "d" are also symmetric but shorter.

Example 3

Input

s = "racecar"

Output

"racecar"

Explanation

The entire string "racecar" is symmetric because it reads the same forwards and backwards. This is the longest possible symmetric substring.

Constraints

1 ≤ s.length ≤ 1000
s consists of only lowercase and uppercase English letters and digits (a-z, A-Z, 0-9).