SOURCE

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

 

// 示例 1：

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

// 输入：s = "cbbd"
// 输出："bb"

const longestPalindrome = function(str) {
    const helper = (arr) => {
        let len = arr.length;
        
        let i = 0;
        let j = len - 1;

        while(i < j) {
            if(arr[i] !== arr[j]) {
                return false;
            };
            
            i+=1;
            j-=1;
        }

        return true;
    }

    const arrayStr = str.split('');
    const len = arrayStr.length;

    const middleIndex = Math.floor(len / 2);

    let result = [];
    let maxLengh = 0;

    let k = 0;

    while(k < middleIndex) {
      for(let j = len;j > 0;j--) {
          const splitArr = arrayStr.slice(k,j);
          const temp = helper(splitArr);
          if(temp && splitArr.length > maxLengh){
              maxLengh = splitArr.length;
              result = splitArr;
              break;
          };
      };
      k +=1;
    };

    return result.join('');
};


const longestPalindrome2 = function(str) {
    if(str.length < 2) {
        return str;
    }

    let len = str.length;
    let maxLengh = 1;
    let start = 0;

    const dp = Array.from({length:len},() =>Array(len).fil(false));
    );

    for(let i = 0;i < len;i++) {
        dp[i][i] = true;
    }

    const arrayStr = str.split('');

    for(let j = 1;j < len;j ++) {
        for(let i = 0;i < len;i ++) {
            if(arrayStr[i] !== arrayStr[j]) {
                dp[i][j] = false;
            }else {
                if(j - i < 3) {
                    dp[i][j] = true;
                }else{
                    dp[i][j] = dp[i + 1][j - 1];
                }
            };

            if(dp[i][j] && j - i + 1 > maxLengh) {
                maxLengh = j- i + 1;
                start = i;
            }
        };
    };

    return str.substring(start,start + maxLengh);

}

const s = "babad"

console.log(longestPalindrome2(s));