LeetCode 5. 最长回文子串

约 5 分钟
文章信息 31 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 历史考题 200-500 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 小米 百度 网易 小红书 快手 滴滴 携程 B站 虾皮 招行 贝壳 商汤 旷视 猿辅导
标签
字符串 动态规划 双指针

题目描述

✅ 5. 最长回文子串

image-20260928184211150

题意分析

在字符串中找出最长的一段连续字符，使它从左往右读和从右往左读完全相同，返回这段子串本身。

子串必须连续，不能跳过字符拼成回文。回文的长度可以是奇数，也可以是偶数；如果有多个同样长的最长回文子串，返回任意一个即可。题目保证输入非空，单个字符也算回文。

解法：中心扩展

核心思路

[!blue]

回文的两侧字符关于中心对称。如果中间一段已经是回文，并且它左右紧邻的字符相同，那么把这两个字符一起纳入后仍然是回文。因此可以从中心出发，不断向两侧扩展，直到越界或遇到不相等的字符。

奇数长度回文的中心是一个字符，从 (i, i) 开始比较；偶数长度回文的中心在两个相邻字符之间，从 (i, i + 1) 开始比较。每个回文都有这两类中心之一，枚举所有位置并检查两类中心，就不会漏掉最长回文。

扩展时左右指针同步向外移动。停止时，两端已经不属于有效回文，真正的区间是 [left + 1, right - 1]，长度为 right - left - 1。每次只保留更长区间的边界，最后再截取字符串，避免反复构造子串。

Java 的扩展函数返回长度，需要从中心 i 还原边界。奇数长度时左右跨度相同；偶数长度时 i 是中间两个字符的左边那个，右侧比左侧多占一位。因此左边界统一为 i - (length - 1) / 2，右边界统一为 i + length / 2，这里的除法都向下取整。Go 直接返回有效区间的左右端点，不需要再换算。

解题步骤

  1. 将答案初始化为首字符，枚举中心位置 i。
  2. 分别从 (i, i) 和 (i, i + 1) 向两侧扩展；下标有效且字符相等时，左指针减一、右指针加一。
  3. 扩展停止后向内退一格，得到当前回文区间；若它更长，就更新答案边界。
  4. Java 根据回文长度换算边界：start = i - (length - 1) / 2、end = i + length / 2；Go 直接使用扩展返回的边界。
  5. 返回从 start 到 end 的子串，截取时右边界使用 end + 1。

代码实现

class Solution {
    public String longestPalindrome(String s) {
        int start = 0;
        int 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(n)$ 个中心，每个中心最多扩展 $O(n)$ 次。
  • 空间复杂度：$O(1)$，只维护扩展指针和答案边界，不计返回结果。

关键点总结

[!green]

  • 奇数和偶数长度回文需要使用两类中心。
  • 扩展停止后指针已越过合法区间一位。
  • 中心扩展比区间 DP 少用 $O(n^2)$ 空间。

易错点总结

[!yellow]

  • 只检查 (i, i)，会漏掉偶数长度回文。
  • 截取字符串时混淆闭区间与左闭右开区间。
  • 空串时下标会越界；本题约束保证字符串非空。

相似题目

题目 难度 关联与区别
647. 回文子串 中等 同样按中心扩展回文区间，原题统计全部回文子串，本题只保留最长区间。
516. 最长回文子序列 中等 原题允许跳过字符形成回文子序列，本题要求连续，不能直接套相同状态。
补充题 216. 最长回文子串的长度 中等 都围绕单个或两个中心向两侧扩展；本题返回子串，补充题只返回长度。
131. 分割回文串 中等 用区间或中心扩展刻画回文结构；本题寻找最长连续回文，该题预处理回文后枚举切分方案。
132. 分割回文串 II 困难 用区间或中心扩展刻画回文结构；本题寻找最长连续回文，该题在回文区间上递推最少切割次数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/44872862
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！