最长回文子串
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
速度
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。回文是指正着读和反着读都一样的字符串。
示例 1
输入：s = "babad"
输出："bab"（"aba" 也是有效答案）
示例 2
输入：s = "cbbd"
输出："bb"
模拟答题者思考
1. 暴力：枚举所有子串再逐个判断是否回文，O(n³)。
2. 回文有对称性：从中心往两边扩展，天然是回文，不必重复判断。
3. 中心有两类：奇数长度以单个字符为中心，偶数长度以两个字符之间为中心。
4. 枚举每个中心（共 2n-1 个）向外扩展，取最长的一段，O(n²) 时间、O(1) 空间。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
l, r | int | 定义：从某中心向两侧扩展时的左右指针 维护：扩展过程中 s[l..r] 始终是回文 更新：只要 s[l]==s[r] 就 l--、r++ |
start,end | int | 定义：目前发现的最长回文子串区间 维护：始终记录最长的一段 更新：某次扩展得到更长回文时更新 |
落码步骤
1. 写一个 expand(l, r)：当 s[l]==s[r] 时 l--、r++，返回最长回文区间
2. 遍历每个 i：以 (i, i) 为中心求奇数回文
3. 以 (i, i+1) 为中心求偶数回文
4. 用更长者更新 start, end，最后返回 s[start:end+1]
代码实现
class Solution:
def longestPalindrome(self, s: str) -> str:
start, end = 0, 0 # 最长回文区间 [start, end]
def expand(l: int, r: int):
# 从中心向两侧扩展，返回最长回文的 (左, 右)
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return l + 1, r - 1
for i in range(len(s)):
l1, r1 = expand(i, i) # 奇数长度中心
if r1 - l1 > end - start:
start, end = l1, r1
l2, r2 = expand(i, i + 1) # 偶数长度中心
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end + 1]class Solution {
public:
string longestPalindrome(string s) {
int start = 0, maxLen = 1;
auto expand = [&](int l, int r) {
while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
if (r - l - 1 > maxLen) { maxLen = r - l - 1; start = l + 1; }
};
for (int i = 0; i < (int)s.size(); i++) {
expand(i, i); // 奇数长度
expand(i, i + 1); // 偶数长度
}
return s.substr(start, maxLen);
}
};
// 时间 O(n²)，空间 O(1)复杂度分析
时间复杂度
O(n²)
空间复杂度
O(1)
常见坑
别漏掉偶数长度中心 (i, i+1)，否则 "bb" 这类会漏解。
扩展结束时循环多走了一步，真正的回文区间是 [l+1, r-1]。
空串或单字符要能正确返回（maxLen 初始设 1，空串单独处理）。
必测边界 Case
Case 1：整体回文
s = "aba" → "aba"
Case 2：无长回文
s = "abc" → "a"（任意单字符）