5. 最长回文子串

力扣题目链接 (opens new window)

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路

最直接的想法是枚举每个子串，再用双指针判断它是否回文。子串有 O(n²) 个，每次判断最多需要 O(n)，总时间就是 O(n³)。

能不能省去反复检查整个子串的时间？回文串从中心向两侧看，字符一定成对相等。 已经知道中间一段是回文时，只需要检查它外侧的两个字符，就能判断扩展后是否仍然回文。

那么，中心一定是一个字符吗？不是。bab 的中心是一个 a，而 bb 的中心在两个 b 之间。每个下标都要尝试两种中心：(i, i) 和 (i, i + 1)。 漏掉双字符中心，示例 2 就找不到 bb。

从中心出发，设左右指针为 left、right：

1. 只要没有越界，且 s[left] == s[right]，就让 left--、right++，继续向外扩展。
2. 扩展停止时，[left + 1, right - 1] 才是最后一个有效的回文区间，长度为 right - left - 1。
3. 如果它比当前答案更长，就记录起点和长度。最后只截取一次答案。

注意停下来的那一刻，left 和 right 已经越过了回文子串的边界。 直接用 [left, right] 截取，会把不匹配的字符也算进去。

模拟过程

先看奇数长度。s = "babad"，选下标 1 的 a 作为中心，left = right = 1。当前回文串是 "a"，接下来同时向两侧移动。

移动到 left = 0、right = 2，两侧都是 b，于是得到 "bab"。再向外移动，left = -1 已越界；最后有效区间仍是 [0, 2]，记录长度 3。

再看偶数长度。s = "cbbd"，选下标 1 和 2 的两个 b 作为中心，先匹配出 "bb"。下一轮比较 c 和 d，不相等，因此最长有效区间是 [1, 2]。

解题代码

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0;
        int maxLen = 0;
        int n = s.size();

        auto expand = [&](int left, int right) {
            while (left >= 0 && right < n && s[left] == s[right]) {
                --left;
                ++right;
            }
            // 停止时两个指针已经越过最后一个有效回文区间
            int len = right - left - 1;
            if (len > maxLen) {
                start = left + 1;
                maxLen = len;
            }
        };

        for (int i = 0; i < n; ++i) {
            expand(i, i);     // 奇数长度：单字符中心
            expand(i, i + 1); // 偶数长度：双字符中心
        }
        return s.substr(start, maxLen);
    }
};

复杂度分析

• 时间复杂度：O(n²)。有 O(n) 个中心，每次最多扩展 O(n) 步。
• 空间复杂度：O(1)，只保存边界和长度；返回的结果字符串不计入额外空间。

其他语言

Python3

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, max_len = 0, 0

        def expand(left: int, right: int) -> None:
            nonlocal start, max_len
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            length = right - left - 1
            if length > max_len:
                start, max_len = left + 1, length

        for i in range(len(s)):
            expand(i, i)
            expand(i, i + 1)
        return s[start:start + max_len]

Java

class Solution {
    private int start = 0;
    private int maxLen = 0;

    public String longestPalindrome(String s) {
        start = 0;
        maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return s.substring(start, start + maxLen);
    }

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

Go

func longestPalindrome(s string) string {
    start, maxLen := 0, 0
    expand := func(left, right int) {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }
        length := right - left - 1
        if length > maxLen {
            start, maxLen = left+1, length
        }
    }
    for i := 0; i < len(s); i++ {
        expand(i, i)
        expand(i, i+1)
    }
    return s[start : start+maxLen]
}

JS

var longestPalindrome = function(s) {
    let start = 0, maxLen = 0;
    const expand = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        const length = right - left - 1;
        if (length > maxLen) {
            start = left + 1;
            maxLen = length;
        }
    };
    for (let i = 0; i < s.length; i++) {
        expand(i, i);
        expand(i, i + 1);
    }
    return s.slice(start, start + maxLen);
};

与代码随想录联系

如果想对照动态规划的做法，可以看主站的5.最长回文子串：其中用 dp[i][j] 表示区间 [i, j] 是否回文，再据此更新最长区间。

建议录友接着做647.回文子串。两题都要判断回文，但 647 题统计所有回文子串的数量，本题只保留最长的一个。做题时也要分清516.最长回文子序列：子串必须连续，子序列可以不连续。