输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
--------
输入: "cbbd"
输出: "bb"

const s = 'abcba';
const r = s.split('').reverse().join('');

if (s === r) return s;

const longestPalinDromeForce = (s) => {
  const len = s.length;
  const cache = []; //  存放所有回文子串

  if (len < 2) return s;

  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      const curr = s.slice(i, j + 1);
      const res = curr.split('').reverse().join('');
      curr === res && cache.push(curr);
    }
  }

  // 所有子串长度递减排序 拿最长的
  const max = cache.sort((a, b) => b.length - a.length)[0];

  return max;
};

longestPalinDromeForce('abbac'); //  输出： abba

longestPalinDromeForce(
  'jrjnbctoqgzimtoklkxcknwmhiztomaofwwzjnhrijwkgmwwuazcowskjhitejnvtblqyepxispasrgvgzqlvrmvhxusiqqzzibcyhpnruhrgbzsmlsuacwptmzxuewnjzmwxbdzqyvsjzxiecsnkdibudtvthzlizralpaowsbakzconeuwwpsqynaxqmgngzpovauxsqgypinywwtmekzhhlzaeatbzryreuttgwfqmmpeywtvpssznkwhzuqewuqtfuflttjcxrhwexvtxjihunpywerkktbvlsyomkxuwrqqmbmzjbfytdddnkasmdyukawrzrnhdmaefzltddipcrhuchvdcoegamlfifzistnplqabtazunlelslicrkuuhosoyduhootlwsbtxautewkvnvlbtixkmxhngidxecehslqjpcdrtlqswmyghmwlttjecvbueswsixoxmymcepbmuwtzanmvujmalyghzkvtoxynyusbpzpolaplsgrunpfgdbbtvtkahqmmlbxzcfznvhxsiytlsxmmtqiudyjlnbkzvtbqdsknsrknsykqzucevgmmcoanilsyyklpbxqosoquolvytefhvozwtwcrmbnyijbammlzrgalrymyfpysbqpjwzirsfknnyseiujadovngogvptphuyzkrwgjqwdhtvgxnmxuheofplizpxijfytfabx',
);

// 输出  暴力解法: 1192.661ms

const str = 'ababc';
// a √
// ab 两端不相等 ×
// aba 两端相等，中间 b 是回文 √
// abab 两端不等 ×
// ...
// b √
// ba 两端不等 ×
// bab 两端相等，中间 a 是回文 √
// ...

const s = 'abbav';
const len = s.length;

// 从尾部开始
for (let i = len - 1; i >= 0; i--) {
  // 内部循环需从当前 i 位置，开始遍历保证截取字符串的顺序
  for (let j = i; j < len; j++) {
    // 内部枚举如下
    // 4 4 v
    // 3 3 a
    // 3 4 av
    // 2 2 b
    // 2 3 ba
    // 2 4 bav
    // 1 1 b
    // 1 2 bb
    // 1 3 bba
    // 1 4 bbav
    // 0 0 a
    // 0 1 ab
    // 0 2 abb
    // 0 3 abba
    // 0 4 abbav
  }
}

const len = s.length;
let cache = []; //  坐标数组

for (let i = len - 1; i >= 0; i--) {
  cache[i] = []; //  初始化 i 位置
  for (let j = i; j < len; j++) {
    if (j - i === 0) {
      //  单个字符
      cache[i][j] = true;
    } else if (j - i === 1 && s[i] === s[j]) {
      //  两个字符
      cache[i][j] = true;
    } else if (s[i] === s[j] && cache[i + 1][j - 1]) {
      //  多个字符
      cache[i][j] = true;
    }

    if (cache[i][j]) {
      console.log('这个区间的字符 就是回文字符');
    }
  }
}

const longestPalindrome = (s) => {
  console.time('最终整合版');
  const len = s.length;
  if (len < 2) return s;

  let cache = [];
  let max = '';

  for (let i = len - 1; i >= 0; i--) {
    cache[i] = [];
    for (let j = i; j < len; j++) {
      if (j - i === 0) {
        cache[i][j] = true;
      } else if (j - i === 1 && s[i] === s[j]) {
        cache[i][j] = true;
      } else if (s[i] === s[j] && cache[i + 1][j - 1]) {
        cache[i][j] = true;
      }

      // 判断长度 替换max
      if (cache[i][j] && j - i + 1 > max.length) {
        max = s.slice(i, j + 1);
      }
    }
  }

  console.timeEnd('最终整合版');
  return max;
};

longestPalindrome(
  'jrjnbctoqgzimtoklkxcknwmhiztomaofwwzjnhrijwkgmwwuazcowskjhitejnvtblqyepxispasrgvgzqlvrmvhxusiqqzzibcyhpnruhrgbzsmlsuacwptmzxuewnjzmwxbdzqyvsjzxiecsnkdibudtvthzlizralpaowsbakzconeuwwpsqynaxqmgngzpovauxsqgypinywwtmekzhhlzaeatbzryreuttgwfqmmpeywtvpssznkwhzuqewuqtfuflttjcxrhwexvtxjihunpywerkktbvlsyomkxuwrqqmbmzjbfytdddnkasmdyukawrzrnhdmaefzltddipcrhuchvdcoegamlfifzistnplqabtazunlelslicrkuuhosoyduhootlwsbtxautewkvnvlbtixkmxhngidxecehslqjpcdrtlqswmyghmwlttjecvbueswsixoxmymcepbmuwtzanmvujmalyghzkvtoxynyusbpzpolaplsgrunpfgdbbtvtkahqmmlbxzcfznvhxsiytlsxmmtqiudyjlnbkzvtbqdsknsrknsykqzucevgmmcoanilsyyklpbxqosoquolvytefhvozwtwcrmbnyijbammlzrgalrymyfpysbqpjwzirsfknnyseiujadovngogvptphuyzkrwgjqwdhtvgxnmxuheofplizpxijfytfabx',
);

//  输出 最终整合版: 19.145ms！！！！