✅5. 最长回文子串 about like-algorithms HOT 2 OPEN

var longestPalindrome = function(s) {
    // dp 解
    if (!s || !s.length) return '';
    let ret = s[0];
    const dp = []; // 二维数组

    for (let i = s.length; i >= 0; i--) { // 倒叙是因为 dp[i] 依赖于 dp[i + 1]
	    dp[i] = [];
	    for (let j = i; j < s.length; j++) {
		    // 特殊情况1：相等时为同一个字符
		    if (j === i) {
			    dp[i][j] = true;
		    } else if (j - i === 1 && s[j] === s[i]) { // 特殊情况2：只有两个的时候，是否相等
			    dp[i][j] = true;
		    } else if (s[i] === s[j] && dp[i + 1][j - 1]) {
			    dp[i][j] = true;
		    }

		    // 当前为真，且长度大于已得到的长度 更新 ret
		    if (dp[i][j] && j - i + 1 > ret.length) {
			    ret = s.slice(i, j + 1);
		    }
	    }
    }

    return ret;
}

function longestPalindrome(s) {
  if (s.length < 2) {
    return s;
  }

  let start = 0;
  let maxLength = 1;

  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > maxLength) {
        maxLength = right - left + 1;
        start = left;
      }
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i - 1, i + 1);
    expandAroundCenter(i, i + 1);
  }

  return s.substring(start, start + maxLength);
}