题目链接 · 灵神原题解（署名来源）

方法一：中心扩展法

最暴力的做法是，枚举所有子串，然后判断子串是否为回文串。由于有 $\mathcal{O}(n^2)$ 个子串，每个子串判断是否回文需要 $\mathcal{O}(n)$，这个做法的时间复杂度是 $\mathcal{O}(n^3)$，太慢了。

能不能 $\mathcal{O}(1)$ 判断一个子串是不是回文的？

比如子串 $\mathtt{\text{abcba}}$，最左边和最右边的字母都是 $\mathtt{\text{a}}$，如果中间的 $\mathtt{\text{bcb}}$ 是回文串，那么我们就能 $\mathcal{O}(1)$ 地知道 $\mathtt{\text{abcba}}$ 是回文串。对于子串 $\mathtt{\text{bcb}}$ 来说，最左边和最右边的字母都是 $\mathtt{\text{b}}$，如果中间的 $\mathtt{\text{c}}$ 是回文串，那么我们就能 $\mathcal{O}(1)$ 地知道 $\mathtt{\text{bcb}}$ 是回文串。显然 $\mathtt{\text{c}}$ 是回文串，所以 $\mathtt{\text{bcb}}$ 是回文串，所以 $\mathtt{\text{abcba}}$ 是回文串。

既然如此，为什么不直接从 $\mathtt{\text{c}}$ 开始向外扩展呢？

• $\mathtt{\text{c}}$ 是回文串。
• 看看 $\mathtt{\text{c}}$ 左右两边的字母是不是一样的，一样，那么 $\mathtt{\text{bcb}}$ 是回文串。
• 继续，看看 $\mathtt{\text{bcb}}$ 左右两边的字母是不是一样的，一样，那么 $\mathtt{\text{abcba}}$ 是回文串。我们 $\mathcal{O}(1)$ 地判断出了一个子串是不是回文串！

这些子串的长度都是奇数，我们称其为奇回文串。

回文串还可以是偶数长度，我们称其为偶回文串。

比如子串 $\mathtt{\text{abccba}}$，我们可以从中间的 $\mathtt{\text{cc}}$ 开始：

• $\mathtt{\text{cc}}$ 是回文串。
• 看看 $\mathtt{\text{cc}}$ 左右两边的字母是不是一样的，一样，那么 $\mathtt{\text{bccb}}$ 是回文串。
• 继续，看看 $\mathtt{\text{bccb}}$ 左右两边的字母是不是一样的，一样，那么 $\mathtt{\text{abccba}}$ 是回文串。

一般地，枚举 $i=0,1,2,\dots ,n-1$ 作为奇回文串的中心，向左右两侧扩展：

• 初始化 $l=r=i$。
• 如果 $s[l]=s[r]$，那么向左右两侧扩展，把 $l$ 减一，把 $r$ 加一，继续判断更长的子串是不是回文串。直到下标出界或者 $s[l]\ne s[r]$。
• 循环结束时，最后一轮循环的子串 $s[l+1]$ 到 $s[r-1]$ 是回文串，若其长度 $r-l-1$ 大于答案的长度，那么更新答案的左右端点为 $l+1$ 和 $r-1$，方便输出具体子串。

同理，枚举 $i$ 和 $i+1$ 作为偶回文串的中心，也就是初始化 $l=i$，$r=i+1$，其余做法同上。

写法一：奇偶分开判断

Python 解法1

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ans_left = ans_right = 0

        # 奇回文串
        for i in range(n):
            l = r = i
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # 循环结束后，s[l+1] 到 s[r-1] 是回文串
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r  # 左闭右开区间

        # 偶回文串
        for i in range(n - 1):
            l, r = i, i + 1
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r  # 左闭右开区间

        return s[ans_left: ans_right]

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int ans_left = 0, ans_right = 0;

        // 奇回文串
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r]) {
                l--;
                r++;
            }
            // 循环结束后，s[l+1] 到 s[r-1] 是回文串
            if (r - l - 1 > ans_right - ans_left) {
                ans_left = l + 1;
                ans_right = r; // 左闭右开区间
            }
        }

        // 偶回文串
        for (int i = 0; i < n - 1; i++) {
            int l = i, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                l--;
                r++;
            }
            if (r - l - 1 > ans_right - ans_left) {
                ans_left = l + 1;
                ans_right = r; // 左闭右开区间
            }
        }

        return s.substr(ans_left, ans_right - ans_left);
    }
};

写法二：合二为一

枚举 $i=0,1,2,\dots ,2n-2$。

• 规定当 $i$ 是偶数时，使用枚举奇回文串的规则，即初始化 $l=r={\displaystyle \frac{i}{2}}$。比如 $i=2$ 时 $l=r=1$。
• 规定当 $i$ 是奇数时，使用枚举偶回文串的规则，即初始化 $l=\lfloor {\displaystyle \frac{i}{2}}\rfloor$，$r=\lceil {\displaystyle \frac{i}{2}}\rceil$。比如 $i=1$ 时 $l=0$，$r=1$。

两种情况可以合并为：

• 初始化 $l=\lfloor {\displaystyle \frac{i}{2}}\rfloor$，$r=\lceil {\displaystyle \frac{i}{2}}\rceil =\lfloor {\displaystyle \frac{i+1}{2}}\rfloor$。

按照这个规则，可以恰好枚举到所有的奇回文串和偶回文串。

Python 解法3

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ans_left = ans_right = 0

        for i in range(2 * n - 1):
            l, r = i // 2, (i + 1) // 2
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # 循环结束后，s[l+1] 到 s[r-1] 是回文串
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r  # 左闭右开区间

        return s[ans_left: ans_right]

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int ans_left = 0, ans_right = 0;

        for (int i = 0; i < 2 * n - 1; i++) {
            int l = i / 2, r = (i + 1) / 2;
            while (l >= 0 && r < n && s[l] == s[r]) {
                l--;
                r++;
            }
            // 循环结束后，s[l+1] 到 s[r-1] 是回文串
            if (r - l - 1 > ans_right - ans_left) {
                ans_left = l + 1;
                ans_right = r; // 左闭右开区间
            }
        }

        return s.substr(ans_left, ans_right - ans_left);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 是 $s$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

方法二：Manacher 算法

具体请看 视频讲解，欢迎点赞关注~

本题需要输出具体的最长回文子串，这需要我们在跑 Manacher 算法的过程中，维护最大的 $\mathit{\text{halfLen}}[i]$ 对应的下标 $\mathit{\text{maxI}}$。最后根据下标转换关系，算出 $t$ 中的最长回文子串在 $s$ 中的下标。具体见视频讲解和代码注释。

Python 解法5

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Manacher 模板
        # 将 s 改造为 t，这样就不需要讨论 len(s) 的奇偶性，因为新串 t 的每个回文子串都是奇回文串（都有回文中心）
        # s 和 t 的下标转换关系：
        # (si+1)*2 = ti
        # ti/2-1 = si
        # ti 为偶数，对应奇回文串（从 2 开始）
        # ti 为奇数，对应偶回文串（从 3 开始）
        t = "#".join("^" + s + "$")

        # 定义一个奇回文串的回文半径=(长度+1)/2，即保留回文中心，去掉一侧后的剩余字符串的长度
        # half_len[i] 表示在 t 上的以 t[i] 为回文中心的最长回文子串的回文半径
        # 即 [i-half_len[i]+1, i+half_len[i]-1] 是 t 上的一个回文子串
        half_len = [0] * (len(t) - 2)
        half_len[1] = 1

        # box_r 表示当前右边界下标最大的回文子串的右边界下标+1
        # box_m 为该回文子串的中心位置
        # 二者的关系为 box_r = box_m + half_len[box_m]
        box_m = box_r = max_i = 0
        for i in range(2, len(half_len)):
            hl = 1
            if i < box_r:
                # 记 i 关于 box_m 的对称位置 i'=box_m*2-i
                # 若以 i' 为中心的最长回文子串范围超出了以 box_m 为中心的回文串的范围
                # 则 half_len[i] 应先初始化为已知的回文半径 box_r-i，然后再继续暴力匹配
                # 否则 half_len[i] 与 half_len[i'] 相等
                hl = min(box_r - i, half_len[box_m * 2 - i])

            # 暴力扩展
            # 算法的复杂度取决于这部分执行的次数
            # 由于扩展之后 box_r 必然会更新（右移），且扩展的的次数就是 box_r 右移的次数
            # 因此算法的复杂度 = O(len(t)) = O(n)
            while t[i - hl] == t[i + hl]:
                hl += 1
                box_m, box_r = i, i + hl

            half_len[i] = hl
            if hl > half_len[max_i]:
                max_i = i

        hl = half_len[max_i]
        # 注意 t 上的最长回文子串的最左边和最右边都是 '#'
        # 所以要对应到 s，最长回文子串的下标是从 max_i-hl+2 到 max_i+hl-2
        # 结合上文的下标转换关系，得到其在 s 上的下标范围是从 (max_i-hl)/2 到 (max_i+hl)/2-2
        return s[(max_i - hl) // 2: (max_i + hl) // 2 - 1]

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    string longestPalindrome(string s) {
        // Manacher 模板
        // 将 s 改造为 t，这样就不需要讨论 s.size() 的奇偶性，因为新串 t 的每个回文子串都是奇回文串（都有回文中心）
        // s 和 t 的下标转换关系：
        // (si+1)*2 = ti
        // ti/2-1 = si
        // ti 为偶数，对应奇回文串（从 2 开始）
        // ti 为奇数，对应偶回文串（从 3 开始）
        string t = "^";
        for (char c : s) {
            t += '#';
            t += c;
        }
        t += "#$";

        // 定义一个奇回文串的回文半径=(长度+1)/2，即保留回文中心，去掉一侧后的剩余字符串的长度
        // half_len[i] 表示在 t 上的以 t[i] 为回文中心的最长回文子串的回文半径
        // 即 [i-half_len[i]+1, i+half_len[i]-1] 是 t 上的一个回文子串
        vector<int> half_len(t.size() - 2);
        half_len[1] = 1;

        // box_r 表示当前右边界下标最大的回文子串的右边界下标+1
        // box_m 为该回文子串的中心位置
        // 二者的关系为 box_r = box_m + half_len[box_m]
        int box_m = 0, box_r = 0, max_i = 0;
        for (int i = 2; i < half_len.size(); i++) {
            int hl = 1;
            if (i < box_r) {
                // 记 i 关于 box_m 的对称位置 i'=box_m*2-i
                // 若以 i' 为中心的最长回文子串范围超出了以 box_m 为中心的回文串的范围
                // 则 half_len[i] 应先初始化为已知的回文半径 box_r-i，然后再继续暴力匹配
                // 否则 half_len[i] 与 half_len[i'] 相等
                hl = min(box_r - i, half_len[box_m * 2 - i]);
            }

            // 暴力扩展
            // 算法的复杂度取决于这部分执行的次数
            // 由于扩展之后 box_r 必然会更新（右移），且扩展的的次数就是 box_r 右移的次数
            // 因此算法的复杂度 = O(t.size()) = O(n)
            while (t[i - hl] == t[i + hl]) {
                hl++;
                box_m = i;
                box_r = i + hl;
            }

            half_len[i] = hl;
            if (hl > half_len[max_i]) {
                max_i = i;
            }
        }

        int hl = half_len[max_i];
        // 注意 t 上的最长回文子串的最左边和最右边都是 '#'
        // 所以要对应到 s，最长回文子串的下标是从 max_i-hl+2 到 max_i+hl-2
        // 结合上文的下标转换关系，得到其在 s 上的下标范围是从 (max_i-hl)/2 到 (max_i+hl)/2-2
        return s.substr((max_i - hl) / 2, hl - 1);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面字符串题单的「三、Manacher 算法」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府