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

/**
 * @method isPalindrome
 * @description 判断字符串s的索引i到索引j是否是回文字符串
 * @param {number} i
 * @param {number} j
 */
const isPalindrome = (i, j) => {
  // 1. 是否是一个字符
  if (i === j) return true;
  // 2. 是否是首尾一致，首尾不一致肯定不是回文字符串
  if (s[i] !== s[j]) return false;
  // 3. 判断索引i和索引j的关系，
  //    基于上面的2条件，走到条件3说明 s[i]和s[j]中间就只有一个字符了，所以这就是一个回文字符串
  if (i + 1 === j) return true;
  // 如果以上条件都不满足，则继续向中间逼近，递归处理
  return isPalindrome(i + 1, j - 1);
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  /**
   * @param {number} i
   * @param {number} j
   */
  const isPalindrome = (i, j) => {
    // 1. 是否是一个字符
    if (i === j) return true;
    // 2. 是否是首尾一致，首尾不一致肯定不是回文字符串
    if (s[i] !== s[j]) return false;
    // 3. 判断索引i和索引j的关系，
    //    基于上面的2条件，走到条件3说明 s[i]和s[j]中间就只有一个字符了，所以这就是一个回文字符串
    if (i + 1 === j) return true;
    // 如果以上条件都不满足，则继续向中间逼近，递归处理
    return isPalindrome(i + 1, j - 1);
  }
  // 缓存字符串s的长度，不必在执行循环时，每次都计算一次。
  const len = s.length;
  // 设置起始索引indexI
  let indexI = 0;
  // 设置结束索引为indexJ
  let indexJ = 0;
  // 两层循环，将每一种子串都枚举
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      // 判断是否是回文字符串
      if (isPalindrome(i, j)) {
        // 如果是回文子串，则将当前长度与历史长度进行比较，取二者的最大值
        if (j - i > indexJ - indexI) {
          // 记录此时的i、j
          indexI = i;
          indexJ = j;
        }
      }
    }
  }
  // 注意审题，返回的是回文子串，不是长度
  return s.substring(indexI, indexJ + 1);
};

// 定义二维数组，缓存结果
const cache = [];
const isPalindrome = (i, j) => {
  // 如果不存在某个一维数组则进行初始化
  if (cache[i] === undefined) {
    cache[i] = [];
  }
  // 如果对应[i][j]存在，则直接返回结果
  if (cache[i][j] !== undefined) {
    return cache[i][j];
  }
  // 1. 是否是一个字符
  if (i === j) return true;
  // 2. 是否是首尾一致，首尾不一致肯定不是回文字符串
  if (s[i] !== s[j]) return false;
  // 3. 判断索引i和索引j的关系，
  //    基于上面的2条件，走到条件3说明 s[i]和s[j]中间就只有一个字符了，所以这就是一个回文字符串
  if (i + 1 === j) return true;
  // 如果以上条件都不满足，则继续向中间逼近，递归处理
  cache[i][j] = isPalindrome(i + 1, j - 1);
  return cache[i][j];
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  const len = s.length;
  const dp = [];
  let [ indexJ, indexI ] = [0, 0];
  for (let i = 0; i < len; i++) {
    if (!dp[i]) {
      dp[i] = []
    }
    dp[i][i] = true;
    // 注意是从j到i，so...
    for (j = 0; j < i; j++) {
      // 在这里要注意dp[i - 1][j + 1]的边界问题
      // 如 cbb，当i=2，j=1时，dp[i - 1][j + 1]的值是dp[1][2]是不存在的 undefined，但是bb确实符合回文字符串
      // 所以要确定 dp[i - 1][j + 1]是否是已经存在的值
      dp[i][j] = s[i] === s[j] ? dp[i - 1]?.[j + 1] ?? true  : false;
      // 判断是否是符合条件，并且长度大于历史最大值
      if (dp[i][j] && (i - j) > (indexI - indexJ)) {
        [indexJ, indexI] = [j, i]
      }
    }
  } 
  return s.substring(indexJ, indexI + 1)
};