Given a string s, return the longest palindromic substring in s.

Note: If there are multiple valid palindromic substrings of the same length, return any of them.

Constraints

• $1 \leq$ s.length $\leq 1000$

• s consist of only digits and English letters.

Let’s take a moment to make sure you have correctly understood the problem. The quiz below helps you check that you are solving precisely the right problem:

Implement your solution in the following coding playground.