最长回文子串 图解题解

最长回文子串在找什么

在字符串 s 中找一段连续的子串，使它正着读和倒着读完全一样，且长度最长，返回这段子串本身。比如 s = "cbbabba" 的答案是 "bbabb"。注意两点：子串必须连续，不是可以跳着选的子序列；答案要的是字符串本身，所以过程中得记住这段回文的起止位置。

为什么逐个检查子串太慢

最笨的办法是枚举所有子串再逐个验证是否回文：子串有 O(n²) 个，每次验证要 O(n)，加起来 O(n³)，字符串一长就没法接受。慢在验证之间毫无信息共享——判断 "bbabb" 时从头比到尾，完全没利用 "bab" 已经是回文这个事实。

其实回文自带一个可用的结构：每个回文都有一个对称中心，从中心向两侧一层层剥开，每层左右字符都相等。反过来，固定中心向外扩，扩到哪里断掉，以它为中心的最长回文就定了。所以换成按中心枚举：每个中心从里往外扩一次，之前从头重验的浪费就没了。

为什么中心有 2n-1 个而不是 n 个

回文分奇偶两种：奇数长度的回文（如 "bab"）中心是一个字符；偶数长度的回文（如 "bb"）中心落在两个相邻字符之间的缝隙上。长度为 n 的字符串有 n 个字符中心、n-1 个缝隙中心，合计 2n-1 个。只枚举字符中心是这题最常见的错误——那样所有偶数长度的回文都找不到，"cbbabba" 里的 "bb"、"abba" 会整批漏掉。

中心扩展每一步为什么是对的

算法过程中始终守着一个不变量（一条自始至终成立的性质）：左右两个位置标记 l、r 能继续向外走，前提是 s[l] 到 s[r] 这一段已经是回文。向外扩一步只新增两端字符，若 s[l-1] 等于 s[r+1]，对称就延续到更大一段；一旦两端不等就停：两端不同的串不可能是回文，再往外扩也救不回来，停下不会漏掉更长的答案。

拿 cbbabba 亲手走一遍

挑两个关键中心走一遍。先看下标 1、2 之间的缝隙：两侧都是 'b'，相等，扩出 "bb"；再往外一层比下标 0 的 'c' 和下标 3 的 'a'，不等，停下，记下 "bb"。真正的答案藏在下标 3 的 'a' 这个奇数中心：自身是 "a"，向外 'b' 对 'b' 扩成 "bab"，再向外 'b' 对 'b' 扩成 "bbabb"，第三层 'c' 对 'a' 不等停下。"bbabb" 长度 5 超过 "bb"，成为最终答案。把 2n-1 个中心都这样过一遍，见过的最长那段就是解。

复杂度多少，哪些边界容易翻车

中心共 2n-1 个，每个最多向外扩约 n/2 层，时间 O(n²)；除了几个下标变量什么都不开，空间 O(1)。另一种同为 O(n²) 的区间动态规划要开二维表记录每段是否回文，中心扩展更省空间也更好写。

边界有三处最容易翻车：扩展循环必须先判 l >= 0 且 r < len(s) 再比较字符，否则越界；截取子串时闭区间长度是 r - l + 1，差一就会截错；若面试官明确要求 O(n)，那是 Manacher（马拉车）算法的领域，复用已经算过的回文半径（每个中心能往外扩多远），实现较复杂，通常在必须线性时才上。

Python

def longestPalindrome(s: str) -> str:
    start, end = 0, 0
    def expand(l, r):
        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)      # 奇数中心
        l2, r2 = expand(i, i + 1)  # 偶数中心
        if r1 - l1 > end - start: start, end = l1, r1
        if r2 - l2 > end - start: start, end = l2, r2
    return s[start:end + 1]

C++

string longestPalindrome(string s) {
    int start = 0, len = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) { l--; r++; }
        if (r - l - 1 > len) { len = r - l - 1; start = l + 1; }
    };
    for (int i = 0; i < s.size(); i++) {
        expand(i, i);      // 奇数中心
        expand(i, i + 1);  // 偶数中心
    }
    return s.substr(start, len);
}

Java

public String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int[] a = expand(s, i, i);      // 奇数中心
        int[] b = expand(s, i, i + 1);  // 偶数中心
        if (a[1] - a[0] > end - start) { start = a[0]; end = a[1]; }
        if (b[1] - b[0] > end - start) { start = b[0]; end = b[1]; }
    }
    return s.substring(start, end + 1);
}
private int[] expand(String s, int l, int r) {
    while (l >= 0 && r < s.length()
           && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return new int[]{l + 1, r - 1};
}