最长回文子串问题 最长回文子串（Longest Palindromic Substring）是字符串算法中的经典问题，要求在一个给定的字符串中，找到最长的回文子串（即正序和倒序相同的连续字符序列）。 例如，对于字符串 "babad" ，最长回文子串为 "bab" 或 "aba" ；对于 "cbbd" ，最长回文子串为 "bb" 。 解题思路（循序渐进） 步骤1：理解回文特性 回文串的核心是 对称性 ： 长度为奇数的回文：中心是单个字符，如 "aba" ，从中心向两边扩展时，左右字符相同。 长度为偶数的回文：中心是两个相同字符，如 "bb" ，从中心向两边扩展时，左右字符相同。 步骤2：暴力解法（Baseline） 最简单的方法是枚举所有子串（共 O(n²) 个），检查每个子串是否为回文（检查需 O(n) 时间），总时间复杂度为 O(n³) 。 不推荐 ，因为对长字符串效率极低。 步骤3：中心扩展法（核心解法） 核心思想是 枚举所有可能的回文中心 ，向两边扩展直到不再满足回文条件。 对长度为 n 的字符串，可能的回文中心有 2n-1 个： 以单个字符为中心：共 n 个（如 s[i] ）。 以两个字符之间的空隙为中心：共 n-1 个（如 s[i] 和 s[i+1] 之间）。 对每个中心，向左右扩展并判断是否相等，记录最大长度和对应的起始位置。 时间复杂度 ： O(n²) （每个中心最多扩展 O(n) 次）。 空间复杂度 ： O(1) （只存储结果）。 实现细节 ： 初始化 start = 0 和 maxLen = 1 （最小回文长度为1）。 遍历每个中心 i ： 对奇数中心： left = i , right = i 。 对偶数中心： left = i , right = i+1 。 扩展函数：当 left >= 0 且 right < n 且 s[left] == s[right] 时， left-- , right++ 。 更新最大长度： len = right - left - 1 ，若 len > maxLen ，则更新 maxLen 和 start （起始位置为 left+1 ）。 返回子串 s[start:start+maxLen] 。 步骤4：动态规划（优化记忆） 定义 dp[i][j] 表示子串 s[i..j] 是否为回文。 状态转移方程： 如果 s[i] == s[j] 且（ j-i <= 2 或 dp[i+1][j-1] == true ），则 dp[i][j] = true 。 否则 dp[i][j] = false 。 初始化：单个字符一定是回文（ dp[i][i] = true ）。 从长度较短的子串向长度较长的子串递推，记录最长回文子串。 时间复杂度 ： O(n²) ， 空间复杂度 ： O(n²) 。 步骤5：Manacher算法（进阶优化） 专门用于解决最长回文子串的线性时间算法。 核心步骤： 预处理 ：在原字符串每个字符间插入分隔符（如 # ），使所有回文长度变为奇数。 维护一个数组 p[i] 表示以 i 为中心的最长回文半径（包括中心）。 利用对称性避免重复计算： 维护当前已知的最右回文边界 right 和对应的中心 center 。 若 i < right ，则 p[i] 可从 p[mirror] 快速初始化，然后继续扩展。 遍历所有中心，更新 p[i] 、 right 和 center ，并记录最大值。 时间复杂度 ： O(n) ， 空间复杂度 ： O(n) 。 示例演示 以字符串 "babad" 为例，用中心扩展法： 中心 i=0 （字符 'b' ）： 奇数扩展：左右都是 'b' ，长度为1。 偶数扩展： (b,a) 不匹配，跳过。 中心 i=1 （字符 'a' ）： 奇数扩展： "bab" （左 'b' ，右 'b' 匹配），长度3 → 更新最大长度。 偶数扩展： (a,b) 不匹配。 中心 i=2 （字符 'b' ）： 奇数扩展： "aba" （左 'a' ，右 'a' 匹配），长度3 → 更新最大长度。 最终得到最长回文子串 "bab" 或 "aba" 。 总结 中心扩展法 ：直观易懂，面试常用。 动态规划 ：适用于需要多次查询子串回文性的场景。 Manacher算法 ：适合对性能要求极高的场景（如处理超长字符串）。