LeetCode 补充题 216. 最长回文子串的长度

约 4 分钟
文章信息 2 个分类 3 个标签
分类
补充题 中等
标签
字符串 动态规划 双指针

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 5. 最长回文子串

LeetCode 原题返回最长回文子串本身；本文只返回长度，并约定空串返回 0。

:::

给定由英文字母和数字组成的字符串 s，返回其最长回文连续子串的长度。

空串返回 0。

示例 1：

输入： s = "babad"
输出： 3
解释： "bab" 和 "aba" 都是长度为 3 的回文子串。

提示：

  • 0 <= s.length <= 1000。

题意分析

回文子串必须连续，其左右两半围绕中心对称。枚举所有单字符中心和相邻字符间的中心，就能覆盖奇数与偶数两类回文，不需要枚举所有子串的两个端点。

解法：中心扩展

核心思路

[!blue]

每个回文都有一个中心。奇数长度以单个字符为中心，偶数长度以相邻两个字符之间为中心；对每个位置都检查这两种情况，就覆盖了全部可能。

expand 从中心向两边同步比较，只要字符相同就继续扩张。结束时左右指针已经各越过有效回文一位，因此有效长度是 right-left-1。主循环保存最长区间，最后只返回其长度。

例如 abba 以中间两个 b 为中心，可以从长度 2 扩到长度 4；只检查单字符中心会漏掉它。空串在进入中心枚举前直接返回 0。

解题步骤

  1. 空串直接返回 0，非空串先将一个字符作为当前最长回文。
  2. 对每个位置 i，分别从 (i,i) 和 (i,i+1) 向外扩展。
  3. 扩展到越界或字符不同时停止，按有效区间长度更新最优区间。
  4. 返回最长区间长度，不复制子串。

代码实现

class Solution {
    public int longestPalindrome(String s) {
        if (s.isEmpty()) {
            return 0;
        }

        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 end - start + 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) int {
    if len(s) == 0 {
        return 0
    }
    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 end - start + 1
}

复杂度分析

  • 时间复杂度：$O(n^2)$。
  • 空间复杂度：额外空间 $O(1)$。

关键点总结

[!green]

分别从单字符和相邻双字符中心向两侧扩展，记录最长区间；最后返回区间长度，而不是截取字符串。

易错点总结

[!yellow]

  • 单字符中心和双字符中心都必须检查，否则会漏掉偶数长度回文。
  • Java 扩展停止时指针已经越过有效区间，长度为 right-left-1；Go 返回的是退回一步后的有效端点。
  • 求的是连续子串，不能跳过不相等的字符继续扩展。

相似题目

题目 难度 关联与区别
5. 最长回文子串 中等 中心扩展或动态规划的回文判断可复用；该题返回最长回文子串本身，本题只返回长度，空串返回 0。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/721653894153
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！