Longest Palindromic Substring

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

A palindrome is a string that reads the same forward and backward.

Examples

Example 1:

Input: s = "babad"

Output: "bab"

Explanation: "aba" is also a valid answer since it has the same length.

Example 2:

Input: s = "cbbd"

Output: "bb"

Explanation: The longest palindromic substring is "bb".

Example 3:

Input: s = "a"

Output: "a"

Explanation: A single character is always a palindrome.

Constraints

• 1 <= s.length <= 1000
• s consists of only lowercase English letters.