Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000s consist of only digits and English letters.
## Solution(Python)
```Python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
left, right = 0, 1
for end in range(0, n):
for start in range(end - 1, -1, -1):
if s[start] == s[end]:
if end - start == 1 or dp[start + 1][end - 1]:
dp[start][end] = True
palindrome_len = end - start + 1
if right - left < palindrome_len:
left = start
right = left + palindrome_len
return s[left: right]
```