中等

问题描述

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

中心扩散

若一个字符串是回文串，那么左右两边添加一个相同的字符，它也是一个回文串，按照回文串长度奇偶性可以分为奇数和偶数长度两种，遍历字符串，以当前遍历到的字符为起点，若左右两个字符相同，则继续往外扩散，直到达到边界或左右两个字符串不一致时停止，这样就得到了以当前字符为中心的奇数长度的回文串。若当前字符与下一个字符相同（若有），则以这两个字符为起点，往外扩散，最终得到偶数长度的回文串。按此枚举所有可能性，即可找出最长的回文子串。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const n = s.length
  let ans = s[0]
  for (let i = 0; i < n; i++) {
    if (i + 1 < n && s[i] === s[i + 1]) {
      let l = i
      let r = i + 1
      while (l - 1 > -1 && r + 1 < n && s[l - 1] === s[r + 1]) {
        l--
        r++
      }
      if (r - l + 1 > ans.length) ans = s.substring(l, r + 1)
    }
    if (i - 1 > -1 && i + 1 < n && s[i - 1] === s[i + 1]) {
      let l = i - 1
      let r = i + 1
      while (l - 1 > -1 && r + 1 < n && s[l - 1] === s[r + 1]) {
        l--
        r++
      }
      if (r - l + 1 > ans.length) ans = s.substring(l, r + 1)
    }
  }
  return ans
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$