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

回文子串是指一个字符串中的子序列，该子序列正读和反读都是一样的。比如 “level”，“abccba”

解题思路

要找到一个字符串中的最长回文子串，可以采用中心扩展法。这种方法的基本思想是从字符串的每个字符（以及每对相邻字符）出发，向两边扩展，直到不再是回文为止。这样可以找到以每个字符为中心的所有回文子串，并从中选出最长的那个。

解题步骤

  1. 边界情况处理：如果字符串长度小于等于1，直接返回原字符串。
  2. 初始化变量：定义变量 max 来临时存储最长回文子串。
  3. 遍历字符串：对于每个字符，尝试两种情况：
    • 以该字符为中心的回文子串（奇数长度）
    • 以该字符及其右边的字符为中心的回文子串（偶数长度）
  4. 扩展回文子串：使用双指针 left 和 right 向两边扩展，检查是否仍然是回文。
  5. 记录最长回文子串：如果 helper 返回的回文子串比已知的最长回文子串还要长，更新 max。
  6. 返回结果：遍历结束后返回 max。

typescript代码实现

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = (s: string) => {
  if (s.length < 2) return s; // 边界条件

  let max: string = ""; // 存储最长回文子串
  for (let i = 0; i < s.length; i++) {
    helper(i, i); // 考虑奇数长度
    helper(i, i + 1); // 考虑偶数长度
  }

  // 辅助函数，寻找回文子串
  function helper(l: number, r: number) {
    while (l >= 0 && r <= s.length - 1 && s[l] === s[r]) {
      l--; // 向左扩展
      r++; // 向右扩展
    }
    const maxStr = s.slice(l + 1, r + 1 - 1);
    if (maxStr.length > max.length) max = maxStr;
  }

  return max;
};

此算法的时间复杂度为 O(n^2) 其中 n 是字符串的长度，因为需要对每个字符尝试构建回文子串并进行比较。空间复杂度为 O(1)。