5. Longest Palindromic Substring

中心扩展

回文串具有中心对称性，其中心可能是一个字符（如 "aba" 的中心是 'b'），也可能是两个字符（如 "abba" 的中心是 "bb"）。

遍历字符串中的每个字符，将其作为回文串的中心，或者将其与下一个字符一起作为中心

向两边扩展，以找出以该中心为基准的最长回文子串。

最后，比较所有找到的回文子串，找出最长的那个。

function longestPalindrome(s) {
  // 获取字符串长度
  const n = s.length
  // 记录最长回文子串的起始索引
  let maxStart = 0
  // 记录最长回文子串的长度
  let maxLength = 0

  // 遍历每个字符，将其作为回文串的中心
  for (let i = 0; i < n; i++) {
    // j = 0: 处理奇数长度的回文串（中心是单个字符）
    // j = 1: 处理偶数长度的回文串（中心是两个相邻字符）
    for (let j = 0; j <= 1; j++) {
      // 左指针，初始指向中心位置
      let l = i
      // 右指针，根据j的值确定初始位置（j=0时和左指针重合，j=1时在左指针右侧）
      let r = i + j

      // 中心扩展：只要左右指针在字符串范围内，且对应字符相等，就继续向两边扩展
      while (l >= 0 && r < n && s.charAt(l) === s.charAt(r)) {
        l-- // 左指针左移
        r++ // 右指针右移
      }

      // 循环结束时，l和r已经超出了回文串的边界，需要回退一步
      l++
      r--

      // 计算当前找到的回文串长度，并和已记录的最长长度比较
      const currentLength = r - l + 1
      if (maxLength < currentLength) {
        maxLength = currentLength // 更新最长长度
        maxStart = l // 更新最长回文串的起始索引
      }
    }
  }

  // 截取并返回最长回文子串（substring的结束索引是开区间，所以要+maxLength）
  return s.substring(maxStart, maxStart + maxLength)
}