方法：动态规划
动态规划的特点：用于求解最优化问题，且每个子集只求一次（而分治法可能会求很多次）
对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串“ababa”，如果我们已经知道 bab 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。
动态规划方程：
也就是说，只有 s[i+1:j-1]s[i+1:j−1] 是回文串，并且 ss 的第 ii 和 jj 个字母相同时，s[i:j]s[i:j] 才会是回文串。
上文的所有讨论是建立在子串长度大于 22 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 11 或 22。对于长度为 11 的子串，它显然是个回文串；对于长度为 22 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = ""
# 枚举子串的长度 l+1
for l in range(n):
# 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
for i in range(n):
j = i + l
if j >= len(s):
break
if l == 0:
dp[i][j] = True
elif l == 1:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
if dp[i][j] and l + 1 > len(ans):
ans = s[i:j+1]
return ans
