0005.最长回文子串
难度：🟡 中等
标签：字符串、动态规划
链接：5. 最长回文子串
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
解题思路
核心思想
本题的目标是在一个字符串中，找到一个最长的、正读和反读都相同的连续子串。解决这个问题的核心在于如何高效地检查所有可能的子串并判断其是否为回文。
思路选择
中心扩展法 是解决此问题的最优思路之一。它的思想是，每一个回文串都有一个中心。这个中心可能是一个字符（对于奇数长度的回文串，如 "aba"），也可能是两个相邻字符之间的空隙（对于偶数长度的回文串，如 "abba"）。
我们可以遍历输入字符串的每一个位置，并以该位置为“中心”，向两边同时扩展，直到不再满足回文条件为止。
通过对每个可能的中心都进行扩展，我们就能找到所有可能的回文子串，并从中找出最长的那一个。
关键步骤
初始化：初始化两个变量
start和end，用于记录当前找到的最长回文子串的起始和结束索引。遍历所有中心：用一个
for循环遍历字符串s的每一个索引i。中心扩展：对于每个索引
i，进行两次中心扩展操作： a. 以i为中心，寻找奇数长度的回文（expandAroundCenter(s, i, i)）。 b. 以i和i+1之间的空隙为中心，寻找偶数长度的回文（expandAroundCenter(s, i, i + 1)）。更新最长回文：比较两次扩展得到的回文长度，取较大者。如果这个长度超过了当前记录的最长回文长度
end - start，则更新start和end的值。定义辅助函数
expandAroundCenter：该函数接收字符串和左右两个指针，从这两个指针开始向两边扩展，直到边界或字符不匹配，然后返回找到的回文串的长度。返回结果：遍历结束后，根据最终的
start和end索引，从原字符串中截取出最长回文子串并返回。
代码实现
/**
* 辅助函数：从给定的中心扩展，寻找回文的长度
* @param {string} s
* @param {number} left
* @param {number} right
* @return {number}
*/
const expandAroundCenter = (s, left, right) => {
// 当 left 和 right 在字符串范围内，并且对应的字符相等时，继续扩展
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--; // 向左扩展
right++; // 向右扩展
}
// 返回回文的长度
return right - left - 1;
}
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
if (s === null || s.length < 1) {
return "";
}
let start = 0, end = 0; // 初始化最长回文子串的起始和结束索引
for (let i = 0; i < s.length; i++) {
// 以 i 为中心，寻找奇数长度的回文
const len1 = expandAroundCenter(s, i, i);
// 以 i 和 i+1 为中心，寻找偶数长度的回文
const len2 = expandAroundCenter(s, i, i + 1);
const len = Math.max(len1, len2);
// 如果当前找到的回文长度大于之前记录的长度
if (len > (end - start)) {
// 更新起始和结束索引
start = i - Math.floor((len - 1) / 2);
end = i + Math.floor(len / 2);
}
}
return s.substring(start, end + 1);
};
复杂度分析
时间复杂度：O(n²) 其中 n 是字符串
s的长度。外层循环遍历 n 次，而每次中心扩展最多需要 O(n) 的时间。空间复杂度：O(1) 我们只使用了常数个额外变量，空间消耗是恒定的。
相关题目
总结
本题是字符串处理中的经典问题。中心扩展法是一种直观且空间效率极高的解决方案，它避免了动态规划解法中 O(n²) 的空间开销。理解如何处理奇数和偶数长度的回文中心，是掌握此算法的关键。