HJ85. 最长回文子串
题目描述
求小写字母字符串的最长回文子串长度。
子串：连续选择一段字符（可全选、可不选）。 回文串：从左往右读和从右往左读是相同的。
输入格式
一行上输入一个长度为 n、仅由小写字母构成的字符串。
输出格式
输出一个整数，表示字符串的最长回文子串的长度。
示例
示例 1
输入：
cdabbacc
输出：
4
说明： "abba" 是最长回文子串。
示例 2
输入：
a
输出：
1
解题思路
第一步：理解问题本质
回文串的核心特征是关于中心对称。例如：
- 奇数长度回文
"abcba"：中心是'c' - 偶数长度回文
"abba"：中心在两个'b'之间
这意味着，如果枚举每个可能的回文中心，向两边扩展，就能找到所有回文子串。
第二步：暴力解法
枚举所有子串，逐一判断是否为回文：
def brute_force(s):
n = len(s)
# ans 至少为 1：单个字符本身就是回文
ans = 1
for i in range(n):
# 枚举所有起点 i 与（闭区间）终点 j，逐个验证
for j in range(i, n):
substr = s[i:j+1]
# 反转后与原串相同即为回文
if substr == substr[::-1]:
ans = max(ans, len(substr))
return ans
时间复杂度：O(n³) —— 枚举 O(n²) 个子串，每个判断 O(n)。
第三步：最优解法 —— 中心扩展法
枚举每个字符作为回文中心，向两边扩展：
- 奇数长度：中心为单个字符
s[i]，左右指针left = right = i - 偶数长度：中心为两个字符之间
s[i]和s[i+1]，左右指针left = i, right = i+1
每次扩展判断 s[left] == s[right]，相等则继续，否则停止。
完整代码实现
算法可视化 · 逐帧回放这道题的代码90 帧 · 录制输入 "cdabbacc"
import sys
def longest_palindrome(s: str) -> int:
"""求字符串的最长回文子串长度（中心扩展法）"""
n = len(s)
if n <= 1:
return n
ans = 1
for i in range(n):
# 情况一：奇数长度回文，中心为 s[i]
left = right = i
while left >= 0 and right < n and s[left] == s[right]:
ans = max(ans, right - left + 1)
left -= 1
right += 1
# 情况二：偶数长度回文，中心在 s[i] 和 s[i+1] 之间
left, right = i, i + 1
while left >= 0 and right < n and s[left] == s[right]:
ans = max(ans, right - left + 1)
left -= 1
right += 1
return ans
if __name__ == "__main__":
for line in sys.stdin:
s = line.strip()
if s:
print(longest_palindrome(s))
示例推演
以输入 "cdabbacc" 为例：
枚举每个中心，扩展过程：
| 中心 i | 奇数扩展 | 偶数扩展 | 更新后的 ans |
|---|---|---|---|
| 0 ('c') | "c" (1) | 无 | 1 |
| 1 ('d') | "d" (1) | 无 | 1 |
| 2 ('a') | "a" (1) | 无 | 1 |
| 3 ('b') | "b" (1) | "bb" (2) | 2 |
| 4 ('b') | "b" (1) | "bb" → "abba" (4) | 4 |
| 5 ('a') | "a" (1) | 无 | 4 |
| 6 ('c') | "c" (1) | "cc" (2) | 4 |
| 7 ('c') | "c" (1) | 无 | 4 |
结果：最长回文子串长度为 4（"abba"）。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力 | O(n³) | O(n) | 枚举所有子串并判断 |
| 中心扩展 | O(n²) | O(1) | 最优解法，只遍历一次 |
| 动态规划 | O(n²) | O(n²) | dp[i][j] 表示子串是否为回文 |
| Manacher | O(n) | O(n) | 线性算法，面试进阶 |
n 为字符串长度
易错点总结
1. 只考虑奇数长度回文
# 错误！只处理了奇数长度
# 偶数长度回文的中心落在两个字符之间，这段代码一次都没枚举到
for i in range(n):
left = right = i
while ...:
# 只处理了以 s[i] 为中心的情况
解决：每个位置需要处理两种情况：奇数中心和偶数中心。
2. 边界越界
# 越界判断必须写在最前面：短路求值保证不会先去访问 s[left] / s[right]
while left >= 0 and right < n and s[left] == s[right]:
注意：必须先判断 left >= 0 和 right < n，再访问 s[left] 和 s[right]。
3. ans 初始值
ans = 1 # 至少单个字符是回文
如果初始化为 0，当输入为空字符串时会返回 0，但题目保证输入非空。
4. 字符串长度为 1
if n <= 1:
return n
单字符本身就是回文，直接返回 1。
扩展思考
Manacher 算法（O(n)）
如果字符串长度很大（如 10⁵），中心扩展的 O(n²) 可能超时。Manacher 算法可以在 O(n) 时间内解决：
- 预处理：在字符间插入特殊字符（如
#），将偶数长度回文转为奇数长度 - 维护一个"最右回文边界"，利用对称性减少重复计算
# Manacher 算法伪代码
def manacher(s):
# 预处理：插入 #
t = '#' + '#'.join(s) + '#'
n = len(t)
p = [0] * n # p[i] = 以 i 为中心的回文半径
center = right = 0
for i in range(n):
if i < right:
# 镜像点 2*center-i 的半径可以直接借用，但不能超过当前右边界
p[i] = min(right - i, p[2 * center - i])
# 从已知半径继续向两侧扩，边界判断放在取值之前
while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i-p[i]-1] == t[i+p[i]+1]:
p[i] += 1
if i + p[i] > right:
# 右端超出已记录的边界时，才值得换中心并把边界推到最右
center, right = i, i + p[i]
return max(p)
动态规划解法
def dp_solution(s):
n = len(s)
# dp[i][j] 表示子串 s[i..j] 是否为回文
dp = [[False] * n for _ in range(n)]
ans = 1
# i 倒序遍历：算 dp[i][j] 要先拿到它左下方的 dp[i+1][j-1]
for i in range(n-1, -1, -1):
dp[i][i] = True
for j in range(i+1, n):
if s[i] == s[j]:
# 首尾相同后看里面那段；长度 2 时里面是空串，直接算回文
dp[i][j] = dp[i+1][j-1] if j - i > 1 else True
if dp[i][j]:
ans = max(ans, j - i + 1)
return ans