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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

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

思路

  1. 回文串有两种情况，偶数长度或奇数长度，分别对应居中字符重复与否，类似 aba、abba
  2. 可在所有字符周边插入一个特殊的辅助字符，使情况统一化（回文串恒为奇数长度），如 #a#b#a#、#a#b#b#a#
  3. 回文字符串恒为奇数长度的情况下，边界情况的处理较容易些
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var longestPalindrome = function (s) {
  const str = '#' + s.split('').join('#') + '#'
  let result = 0
  let startIndex = 0
  for (let i = 1; i < str.length; ++i) {
    let length = 1
    for (let j = 1; j <= i && i + j < str.length; ++j) {
      if (str[i - j] !== str[i + j]) {
        break
      }
      length += 2
    }
    if (length > result) {
      result = length
      startIndex = i - (length - 1) / 2
    }
  }
  return str.substring(startIndex, startIndex + result).replace(/#/g, '')
}