Longest Palindromic Substring
你会得到一个由小写英文字母组成的字符串 s。请返回它最长的回文子串：一段连续的字母，从前往后读和从后往前读都相同。如果有多个子串的长度相同且都是最长的，请返回最靠左的那个。
函数
- sstring
- 要搜索的小写字符串
- 返回值string
- s 的最长回文子串；如果有多个并列最长，取最靠左的那个
约束条件
1 ≤ s.length ≤ 2000s只包含小写英文字母。- 如果有多个最长回文，答案是起始索引最小的那个。
示例
- 输入
- s = "bananas"
- 输出
- "anana"
- 解释
"anana"正着读和反着读都一样，而且有 5 个字母。所有更长的片段两端都不匹配："banana"（b，a）、"ananas"（a，s）和"bananas"（b，s）。
- 输入
- s = "xyzzyabba"
- 输出
- "yzzy"
- 解释
"yzzy"和"abba"都是长度为 4 的回文串，而且不存在更长的回文串。"yzzy"从索引 1 开始，早于从索引 5 开始的"abba"，所以并列时它胜出。
- 输入
- s = "abcd"
- 输出
- "a"
- 解释
- 没有两个字母相同，因此每个回文都只有一个字母。最左边的回文是
"a"。
进阶
你能在 O(n) 时间内找到答案吗？
提示
逐个打开提示，每个都会多透露一点。
每个回文串都以其中间位置为轴对称。看看
"aba"和"abba"：它们各自的中间位置在哪里？长度为 n 的字符串有多少种可能的中间位置？从中间开始。如果它两侧的字母相同，你就得到了一个比之前长两个字母的回文。什么时候必须停止扩展？为什么不可能有更长的回文也以这里为中心？
对于
2n-1个中心中的每一个（每个字母以及相邻两个字母之间的间隙），在两侧字母相同的情况下向外扩展，并记住最长的结果。只有新回文串严格更长时才替换当前最佳结果，这样长度相同时最靠左的回文串会胜出。
题解
回文串以中间位置为轴对称：奇数长度的回文串以一个字母为中心，例如 "anana"；偶数长度的回文串以两个相同字母之间的间隙为中心，例如 "abba"。从中心向两侧扩展每个回文串，每次比较都会扩展一个已找到的回文串：时间复杂度为 O(n²)，额外空间复杂度为 O(1)；而逐个检查所有子串的时间复杂度为 O(n³)。
检查每个子字符串
结果正确，但无法在最大的测试中运行完毕
思路
固定起点 i 和终点 j，然后从两端向内比较字母，直到两个字母不同或两个指针相遇。尝试所有 n(n+1)/2 个子字符串，不会漏掉答案。起点从左到右依次移动，只有在找到更长的回文时才替换当前最佳结果，这样就能保留最靠左的回文。
每次测试最多需要遍历子字符串的一半。对于 2000 个 a，每个子字符串都是回文：大约需要 n³/12 ≈ 6.7 × 10^8 次字母比较。
算法
- 先把第一个字母作为当前最佳结果：起点为 0，长度为 1。
- 对于每个起点
i和每个终点j ≥ i，从两端向中间比较字母，直到它们不同或两个指针相遇。 - 如果没有一对字母不同，并且
j-i+1大于当前最佳长度，就记录i和该长度。 - 返回从最佳起点开始、长度为最佳长度的子字符串。
def longestPalindrome(s):
n = len(s)
best_start, best_len = 0, 1
for i in range(n):
for j in range(i, n):
# Compare s[i..j] from both ends toward the middle
left, right = i, j
while left < right and s[left] == s[right]:
left += 1
right -= 1
is_palindrome = left >= right
if is_palindrome and j - i + 1 > best_len:
best_start, best_len = i, j - i + 1
return s[best_start:best_start + best_len]按长度排列的回文表
思路
测试 "anana" 时，会先比较 a 和 a，再比较 n 和 n，而第二次比较就是对 "nan" 的完整测试。把每个答案都存起来：当 s[i..j] 的两端相同，且 s[i+1..j-1] 是回文时，s[i..j] 就是回文。
按长度填充表格 pal[i][j]。单个字母是回文，两个字母在相同时是回文，而更长的单元格会读取短两个字母的单元格，后者已经填好。在 "bananas" 中，pal[1][5] 成立，因为 s[1] 和 s[5] 都是 a，而且 pal[2][4]（"nan"）也成立。同一长度内，起始位置从左到右排列，因此最长记录长度的第一个回文是最靠左的。
大约 n²/2 个单元格，每个单元格的操作耗时为 O(1)，总耗时为 O(n²)。代价是内存：当 n = 2000 时，需要 4 × 10^6 个单元格。
算法
- 创建一个 n × n 的表
pal，初始值全部为 false。 - 对于从 1 到 n 的每个长度，以及每个结束位置
j = i+length-1仍在字符串范围内的起始位置i，比较s[i]和s[j]。 - 如果它们相同，并且长度不超过 2，或者
pal[i+1][j-1]为 true，就将pal[i][j]标记为 true。 - 当某个被标记单元格的长度超过当前最佳长度时，记录
i和该长度。 - 返回从最佳起始位置开始的子字符串。
def longestPalindrome(s):
n = len(s)
# pal[i][j] is True when s[i..j] reads the same both ways
pal = [[False] * n for _ in range(n)]
best_start, best_len = 0, 1
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1
# Equal ends, and the part inside them is a palindrome (or too short to matter)
if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
pal[i][j] = True
if length > best_len:
best_start, best_len = i, length
return s[best_start:best_start + best_len]围绕每个中心展开
思路
一个由 n 个字母组成的字符串有 n 个字母中心和 n-1 个间隙中心，总共 2n-1 个。从一个中心开始向外逐步扩展，直到两边的字母不匹配。第一次不匹配或到达边缘时，扩展就结束，因为更长的回文都会包含这对不匹配的字母。因此，每个中心扩展一次，就能找到以该中心为中心的最长回文。
在 "bananas" 中，从索引 3 开始扩展，n 和 n 匹配，a 和 a 也匹配，然后在 b 和 s 处停止：长度为 5，起始位置是 3 - (5-1)/2 = 1，因此结果是 "anana"。两个长度相同的回文奇偶性相同，所以中心位置靠前的回文起始位置也更靠前。从左到右遍历各个中心，并且只在长度严格更长时才更新当前最长回文。
最坏情况是所有字母都相同：当 n = 2000 时，大约需要 n²/2 = 2 × 10^6 步，内存只需存储几个整数。
算法
- 编写
expand(left, right)：当两个索引都在字符串范围内且对应字母相同时，将left向下移动，将right向上移动。返回right-left-1。 - 对于从 0 到 n-1 的每个中心，取
expand(center, center)和expand(center, center+1)中较大的值。 - 如果该长度大于当前最佳长度，就将最佳起始位置设为向下取整后的
center - (length-1)/2，并将最佳长度设为该长度。 - 返回从最佳起始位置开始、长度为最佳长度的子字符串。
def expand(s, left, right):
# Grow outward while the two ends match; return the palindrome's length
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
def longestPalindrome(s):
best_start, best_len = 0, 1
for center in range(len(s)):
# Odd lengths grow from one letter, even lengths from the gap after it
length = max(expand(s, center, center), expand(s, center, center + 1))
if length > best_len:
best_start = center - (length - 1) // 2
best_len = length
return s[best_start:best_start + best_len]
易错点和边界情况
- 只围绕字母扩展会漏掉所有偶数长度的回文：
"abba"会返回"a"。 - 遍历会在越过两端一步后停止，因此长度是
right-left-1。使用right-left+1会把两个不匹配的字母也算进去。 - 长度相同时替换当前最佳结果，会返回最右侧的回文：对于
"xyzzyabba"，返回"abba"而不是"yzzy"。 - 对于间隙中心，
center - length/2会多向左偏一个位置。在"xyzzyabba"中，索引 2 后的间隙给出的长度是 4，起始位置是2 - (4-1)/2 = 1，而不是 0。 - 按起始位置从 0 开始填充表格时，会在
pal[i+1][j-1]设置之前读取它。按长度填充，或从末尾开始遍历起始位置。
常见问题3
最长回文子串的时间复杂度是多少？
从中心向两侧扩展需要 O(n²) 的时间和 O(1) 的额外内存。回文表同样需要 O(n²) 的时间，但会存储 n² 个单元格，而单独检查每个子字符串则需要 O(n³) 的时间。
你应该使用动态规划还是从中心向两侧扩展？
从中心向两边扩展。两种方法的时间复杂度都是 O(n²)，但对于 n = 2000，表格会占用 4 × 10^6 个单元格，而扩展只需要保存几个整数。扩展还会在遇到第一个不匹配时停止，因此对于回文数量较少的字符串，它所需的步骤远少于 n²。
最长回文子串和最长回文子序列有什么区别？
子字符串是一段连续的字母，而子序列可以跳过一些字母。在 "character" 中，最长回文子字符串是 "ara"，而 "carac" 是长度为 5 的回文子序列。子序列问题会使用一个以 (i, j) 为索引的表，当两端不同时舍弃其中一端。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def longestPalindrome(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "bananas"
预期输出
"anana"