如何在 JavaScript 字符串中找到最长的回文子字符串？

在字符串处理问题中，回文字符串（Palindrome） 是一种非常经典的模式：一个字符串如果正着读和反着读完全一样，它就是回文字符串，例如 'racecar' 或 'abba'。

在实际开发中，我们经常需要找到一个字符串中最长的回文子字符串（Longest Palindromic Substring），这不仅考验我们的算法能力，也训练我们对于双指针、中心扩展等技术的掌握。

⚠ 本文不涉及 Manacher 算法（最优 O(n) 解决方案），而是注重于常见算法思维和实战技巧的掌握。

🔍 一、什么是回文字符串？

判断一个字符串是否是回文非常简单。可以直接反转它然后与原始字符串进行比较：

const isPalindrome = str => {
  const reversed = str.split('').reverse().join('');
  return str === reversed;
};

isPalindrome('racecar'); // true
isPalindrome('abba');    // true
isPalindrome('hello');   // false

🧨 二、暴力破解法（Brute Force）

最直观的方式是穷举所有可能的子字符串，然后依次判断它们是否是回文，保留其中最长的那一个。

实现思路：

使用两个指针枚举所有子串。
检查是否为回文。
更新最长结果。

const longestPalindrome = str => {
  let best = { length: 0, value: '' };
  for (let l = 0; l < str.length; l++)
    for (let r = l + best.length; r < str.length; r++) {
      const current = { length: r - l, value: str.slice(l, r + 1) };
      if (!isPalindrome(current.value)) continue;
      if (current.length < best.length) continue;
      best = current;
    }
  return best.value;
};

longestPalindrome('babad'); // 输出 'bab' 或 'aba'
longestPalindrome('cbbd');  // 输出 'bb'

复杂度分析：

时间复杂度：O(n^3)
空间复杂度：O(n)（字符串切片时）

❗暴力法虽然直观，但效率非常低，无法应对大规模数据。

💡 三、中心扩展法（Expand Around Center）

我们可以将每个字符（甚至字符间的空隙）作为“回文中心”，从中心向两边扩展，查找最大长度的回文。

回文扩展核心函数：

const expandAroundCenter = (str, left, right) => {
  while (left >= 0 && right < str.length && str[left] === str[right]) {
    left--;
    right++;
  }
  return {
    left: left + 1,
    right: right - 1,
    length: right - left - 1
  };
};

判断字符串是否为回文：

const isPalindrome = str => {
  const centerPoints = (str.length % 2 === 0)
    ? [str.length / 2 - 1, str.length / 2]
    : [Math.floor(str.length / 2), Math.floor(str.length / 2)];
  const maxPalindrome = expandAroundCenter(str, ...centerPoints);
  return maxPalindrome.length === str.length;
};

🚀 四、最终高效实现（推荐方法）

将中心扩展方法应用到字符串的每一个位置，以捕获最长的回文子串。

const expandAroundCenter = (str, left, right) => {
  while (left >= 0 && right < str.length && str[left] === str[right]) {
    left--;
    right++;
  }
  return { left: left + 1, right: right - 1, length: right - left - 1 };
};

const longestPalindrome = str => {
  let best = { left: 0, right: 0, length: 0 };
  for (let i = 0; i < str.length; i++) {
    const odd = expandAroundCenter(str, i, i);
    const even = expandAroundCenter(str, i, i + 1);
    const current = odd.length > even.length ? odd : even;
    if (current.length > best.length) best = current;
  }
  return str.slice(best.left, best.right + 1);
};

longestPalindrome('babad'); // 输出 'bab' 或 'aba'
longestPalindrome('cbbd');  // 输出 'bb'

复杂度分析：