LeetCode 5. 最长回文子串

2026-09-09 HGNULB 约 4 分钟

文章信息 30 个分类 6 个标签

分类

LeetCode CodeTop 中等已解决已掌握历史考题 200-500 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴京东华为拼多多网易小米商汤旷视虾皮携程哔哩哔哩小红书贝壳 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 5. 最长回文子串

题意分析

输入一个字符串 s，要求返回它的最长回文子串本身，而不是长度。回文的含义是正读与反读完全一致。

第一个关键词是「子串」：子串必须是连续的一段，取定下标区间 [left, right] 后，里面的字符一个都不能跳过。这和「子序列」有本质区别——"abcda" 里挑出 a、c、a 能组成一个长度 3 的回文子序列，但它们在原串中并不相邻，不构成回文子串（该串真正的最长回文子串只有单个字符）。凡是允许「挑着取」的做法都会高估答案。

第二个关键词是「对称」：回文一定是从中心向两侧镜像展开的，而中心有两种形态。"aba" 这类奇数长度回文的中心落在某个字符上；"bb" 这类偶数长度回文的中心落在两个字符之间的缝隙里。长度为 $n$ 的串有 $n$ 个字符位置和 $n - 1$ 条内部缝隙，两类中心都必须考虑，否则所有偶数长度的答案都会被整体漏掉。

边界情形有几个：单个字符本身就是回文，所以答案长度至少为 1，不存在「找不到回文」的情况；"abcd" 这种没有任何长度大于 1 的回文的串，返回任意一个单字符都算对；"aaaa" 这种全部字符相同的串，答案是整个串，任何「找到一个就提前收工」的剪枝都会出错；当存在多个等长的最长回文时（如 "babad" 里的 "bab" 与 "aba"），返回其中任意一个即可。

题面本身没有给出可利用的特殊结构，唯一的算法信号来自回文性质的自相似性：把一个回文的首尾两个字符同时去掉，剩下的部分仍然是回文；反之，给一个回文的两端补上一对相同字符，得到的还是回文。这条性质是所有高效解法的入口，因为它把「长区间的判定」与「短区间的判定」直接连了起来。

解法：中心扩展

核心思路

回文串由中心向两侧对称扩展。分别枚举每个字符作为奇数长度中心，以及相邻字符之间作为偶数长度中心，记录最长区间。

解题步骤

枚举中心位置 i。

分别扩展 (i, i) 和 (i, i + 1)。

两侧字符相等就继续扩展，越界或不等时停止。

若当前回文更长，更新答案的左右边界。

代码实现

class Solution {
    public String longestPalindrome(String s) {
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            int length = Math.max(expand(s, i, i), expand(s, i, i + 1));
            if (length > end - start + 1) {
                start = i - (length - 1) / 2;
                end = i + length / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length()
                && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

func longestPalindrome(s string) string {
    start, end := 0, 0

    expand := func(left, right int) (int, int) {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }
        return left + 1, right - 1
    }

    for i := 0; i < len(s); i++ {
        for _, center := range [][2]int{{i, i}, {i, i + 1}} {
            left, right := expand(center[0], center[1])
            if right-left > end-start {
                start, end = left, right
            }
        }
    }
    return s[start : end+1]
}

复杂度分析

时间复杂度：$O(n^2)$。

空间复杂度：$O(1)$，不计返回结果。

关键点总结

奇数和偶数长度回文需要使用两类中心。

扩展停止后指针已越过合法区间一位。

中心扩展比区间 DP 少用 $O(n^2)$ 空间。

易错点总结

只检查 (i, i)，会漏掉 "abba" 这类偶数长度回文。

截取字符串时混淆闭区间与左闭右开区间。

空串时下标会越界；本题约束保证字符串非空。

相似题目

题目	难度	考察点
647. 回文子串	中等	中心一样要枚举，但要累加每个中心撑出的回文个数而不是取最长
LCR 020. 回文子串	中等	与 647 同题换编号，同样求回文子串总数，可直接复用本题的扩展函数
516. 最长回文子序列	中等	把「连续子串」放宽成可跳字符的子序列，中心不再唯一，只能区间 DP
131. 分割回文串	中等	要输出把整串切成回文段的所有方案，本题的回文表变成回溯的剪枝依据
214. 最短回文串	困难	只关心以下标 0 开头的最长回文前缀，再把剩余部分反转后补到串首
125. 验证回文串	简单	只判定单个串是否回文，难点在跳过非字母数字字符并忽略大小写
9. 回文数	简单	判定对象是整数，进阶要求不借助字符串，用取余与反转数字做对称判断