5. 最长回文子串#

大家好！今天我们来探讨一道经典的字符串算法问题——最长回文子串。这个问题不仅在面试中常见，也是理解字符串处理和多种算法技巧的绝佳窗口。让我们一起探索回文字符串的奇妙世界！

🌟 什么是回文？从生活到算法#

在深入算法之前，让我们先理解什么是回文。回文是指正着读和倒着读都一样的序列。比如：

“上海自来水来自海上”
“madam”
“racecar”
“12321”

回文结构在自然界和人类艺术中广泛存在，展现了一种完美的对称之美。在算法世界中，寻找最长回文子串则是对这种对称性的一种探索。

问题描述#

题目目标#

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

示例 1#

输入： s = "babad" 输出： "bab" 说明： “aba” 也是一个有效答案

🎯 问题描述：寻找对称的最长片段#

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

例如：

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

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

plaintext

🤔 从小例子开始思考#

让我们通过分析几个简单例子来理解这个问题：

例子1: “aba”

回文子串有: “a”, “b”, “a”, “aba”
最长的是 “aba”，长度为3

例子2: “abbc”

回文子串有: “a”, “b”, “b”, “c”, “bb”
最长的是 “bb”，长度为2

通过这些例子，我们发现回文有两种结构：

奇数长度，形如 “aba”，有一个中心字符
偶数长度，形如 “abba”，有两个中心字符

💡 解决方案：多种思路的碰撞#

方法一：中心扩展法#

中心扩展法的核心思想是：对于字符串中的每个位置，我们将其视为回文的中心，然后向两边扩展，直到不再形成回文。

class Solution {
    public String longestPalindrome(String s) {
        // 边界条件：空字符串或 null 时，没有可取的回文子串，返回空串
        if (s == null || s.length() < 1) return "";

        // start 记录当前已知最长回文子串的起始下标
        // end 记录当前已知最长回文子串的结束下标
        int start = 0, end = 0;
        // 枚举每个位置 i，把它当作“回文中心”来向两边扩展
        for (int i = 0; i < s.length(); i++) {
            // 以单个字符 i 为中心扩展，得到奇数长度回文的长度
            int len1 = expandAroundCenter(s, i, i);
            // 以 i 和 i+1 之间为中心扩展，得到偶数长度回文的长度
            int len2 = expandAroundCenter(s, i, i + 1);
            // 当前中心可得到的最长回文长度
            int len = Math.max(len1, len2);

            // 如果找到了更长回文，则更新全局最优区间 [start, end]
            if (len > end - start) {
                // 对于长度 len 的回文，中心在 i 时，左边界计算如下
                start = i - (len - 1) / 2;
                // 右边界计算如下
                end = i + len / 2;
            }
        }

        // substring 的右边界是开区间，所以要传 end + 1
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        // 当左右指针都不越界，且两侧字符相等时，继续向外扩展
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // 左指针左移，尝试扩展更大的对称区间
            left--;
            // 右指针右移，尝试扩展更大的对称区间
            right++;
        }
        // 循环结束时，left/right 已经越过有效回文边界各 1 位
        // 有效回文长度 = (right - 1) - (left + 1) + 1 = right - left - 1
        return right - left - 1;
    }
}

java

时间复杂度：O(n²)，每个中心最多扩展n次空间复杂度：O(1)，只使用了常数额外空间

方法二：动态规划#

动态规划的思路是：如果一个字符串是回文，那么去掉首尾字符后仍是回文。我们可以用一个二维数组dp[i][j]表示子串s[i…j]是否为回文。

状态转移方程：

dp[i][j] = true，如果s[i] == s[j] 且 (j-i <= 2 或 dp[i+1][j-1] == true)

class Solution {
    public String longestPalindrome(String s) {
        // n 表示字符串长度
        int n = s.length();
        // dp[i][j] 表示子串 s[i...j] 是否是回文串
        boolean[][] dp = new boolean[n][n];
        // result 保存当前找到的最长回文子串
        String result = "";

        // 长度为 1 的子串一定是回文，先初始化对角线
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            // 当字符串非空时，先给 result 一个合法初值（任意单字符）
            result = s.substring(i, i+1);
        }

        // 检查所有长度为 2 的子串：两个字符相等则为回文
        for (int i = 0; i < n-1; i++) {
            if (s.charAt(i) == s.charAt(i+1)) {
                dp[i][i+1] = true;
                // 更新当前最长回文
                result = s.substring(i, i+2);
            }
        }

        // 检查长度 >= 3 的子串，并按长度从小到大递推
        for (int len = 3; len <= n; len++) {
            // i 是子串起点，j 是子串终点，满足 j = i + len - 1
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                // 首尾字符相等，且去掉首尾后的内部子串也是回文 => 当前是回文
                if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {
                    dp[i][j] = true;
                    // 只有更长时才更新结果，保证 result 始终是当前最长回文
                    if (len > result.length()) {
                        result = s.substring(i, j+1);
                    }
                }
            }
        }

        // 返回最终最长回文子串
        return result;
    }
}

java

时间复杂度：O(n²) 空间复杂度：O(n²)，需要n²大小的dp数组

方法三：Manacher算法#

Manacher算法是一种线性时间复杂度的解法，它通过巧妙地利用回文的对称性，避免了不必要的重复计算。

class Solution {
    public String longestPalindrome(String s) {
        // 边界条件：空字符串或 null 直接返回空串
        if (s == null || s.length() < 1) return "";

        // 预处理：在每个字符间插入 '#'，统一奇偶回文处理逻辑
        StringBuilder sb = new StringBuilder();
        // 先放一个 '#'，让首字符也能被“夹在中间”
        sb.append('#');
        // 把原串变成形如 #a#b#b#a# 的结构
        for (char c : s.toCharArray()) {
            sb.append(c).append('#');
        }
        // t 是预处理后的新串
        String t = sb.toString();

        // n 是预处理后字符串长度
        int n = t.length();
        // p[i] 表示以 i 为中心的回文“半径”（不含中心本身）
        int[] p = new int[n];
        // center 是当前已知最右回文的中心
        // right 是当前已知最右回文的最右边界
        int center = 0, right = 0;
        // maxLen 记录最长回文半径
        // maxCenter 记录对应中心位置
        int maxLen = 0, maxCenter = 0;

        for (int i = 0; i < n; i++) {
            // 若 i 落在当前最右回文内部，可利用对称点信息给 p[i] 一个下界
            if (right > i) {
                // i 关于 center 的对称点是 2 * center - i
                // p[i] 至少可扩到 min(对称点半径, 右边界剩余长度)
                p[i] = Math.min(p[2 * center - i], right - i);
            }

            // 在已有半径基础上继续向两侧扩展
            while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && 
                   t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) {
                // 两侧字符相等，半径 +1
                p[i]++;
            }

            // 如果以 i 为中心的回文右边界更靠右，则更新 center 和 right
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }

            // 维护全局最长回文信息
            if (p[i] > maxLen) {
                maxLen = p[i];
                maxCenter = i;
            }
        }

        // 把预处理串中的区间映射回原串起点
        int start = (maxCenter - maxLen) / 2;
        // 原串中的最长回文长度就是 maxLen
        return s.substring(start, start + maxLen);
    }
}

java

时间复杂度：O(n)，每个位置最多被访问两次空间复杂度：O(n)，需要存储处理后的字符串和p数组

🎨 图解算法：直观理解过程#

中心扩展法图解#

以字符串”babab”为例：

   b a b a b
   0 1 2 3 4

1. 以index=0为中心扩展：
   只有"b"，长度1

2. 以index=1为中心扩展：
   "a"，长度1

3. 以index=2为中心扩展：
   "b" -> "bab" -> "babab"，长度5

4. 以index=3和index=4之间扩展(偶数中心)：
   无法形成回文

最长回文子串："babab"，长度5

plaintext

动态规划填表图解#

以”babad”为例：

  | b | a | b | a | d
--+---+---+---+---+---
b | T | F | T | F | F
a |   | T | F | T | F
b |   |   | T | F | F
a |   |   |   | T | F
d |   |   |   |   | T

plaintext

填表过程：

对角线全部为T（单个字符都是回文）
检查相邻两个字符：dp[0][1] = F, dp[1][2] = F, dp[2][3] = F…
检查长度为3的子串：如”bab”，因为首尾相同且中间是回文，所以dp[0][2] = T
依此类推…

最长回文子串：“bab”，长度3

📊 算法比较：选择最适合的武器#

	中心扩展法	动态规划	Manacher算法
时间复杂度	O(n²)	O(n²)	O(n)
空间复杂度	O(1)	O(n²)	O(n)
实现难度	简单	中等	较复杂
适用场景	一般情况	需要记录所有回文	追求极致性能

💫 优化与变体：应对不同挑战#

优化一：减少重复计算#

在中心扩展法中，我们可以记录已经计算过的结果，避免重复扩展。

优化二：预处理特殊情况#

对于全部相同字符的字符串如”aaaaa”，我们可以直接返回整个字符串。

变体一：计算回文子串的数量#

除了最长回文子串，有时我们需要计算所有的回文子串数量，这时动态规划方法更为适合。

变体二：允许删除一个字符#

如果允许删除一个字符使得结果是回文，问题会变得更加复杂，需要修改我们的算法。

🌈 应用场景：回文算法的广泛应用#

回文问题在实际中有许多应用：

文本分析和自然语言处理
DNA序列分析中的回文结构
回文密码和加密算法
数据存储和检索中的哈希算法

🎓 面试指南：应对回文相关问题#

面试中遇到回文问题时：

先确认问题类型（最长回文、回文判断、回文数量等）
考虑时间和空间限制，选择合适的算法
注意边界情况（空字符串、单字符、全相同字符等）
清晰表达算法思路，从简单方法开始，逐步优化

🔍 延伸阅读：回文算法的更多探索#

回文链表的判断
回文对（Palindrome Pairs）
最长回文子序列（可以不连续）
构造回文的最小插入次数

🤔 思考题#

如果允许重新排列字符串中的字符，如何找到可以形成的最长回文？

回文问题展示了算法之美，从简单的中心扩展到复杂的Manacher算法，我们看到了如何通过不同视角解决同一问题。希望这篇文章能帮助你掌握回文算法的精髓，在面试和实际应用中得心应手！

补充：Manacher算法的思维突破#

Manacher算法是解决回文问题的”终极武器”，它的核心在于利用已计算回文的信息来加速新回文的判定。想象我们已经找到了一个以center为中心、半径为right的回文，对于在这个范围内的新位置i，可以利用i关于center的对称点j的已知回文信息！

这种对称性利用使得算法能在线性时间内找到最长回文子串，是算法设计中”利用已知信息减少重复计算”的典范。

对于面试中不要求极致性能的场景，中心扩展法通常是最佳选择，因为它简单直观且空间效率高，能很好地平衡复杂度与实现难度。

回文问题的美妙之处在于，它将对称性这个数学概念与字符串处理完美结合，而掌握它的各种解法，将帮助我们构建更丰富的算法思维工具箱！