5.最长回文子串：
给你一个字符串s，找到s中最长的回文子串？

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

示例 2： 输入：s = “cbbd” 输出：”bb”

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

方法

暴力解法

动态规划

⭐️中心扩展算法

思路
依次将每个数作为回文子串的中心，向两边扩散，若左/右的值和中心的值相等，则中心可能为多个相同的数（如‘abccba’, 回文中心为’cccc’），提前移动左/右到它与中心值不再相等为止，然后再看是否还是回文串。
算法

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
    let res = '';
    for (let i = 0; i < s.length; i++) {
        // 寻找长度为奇数的回文子串(以当前元素向两边扩散)
        const s1 = palindrome(s, i, i);
        // 寻找长度为偶数的回文子串(以s[i],s[i + 1])向两边扩散
        const s2 = palindrome(s, i, i + 1);
        res = res.length > s1.length ? res : s1;
        res = res.length > s2.length ? res : s2;
    }
    return res;
};
function palindrome(s, l, r) {
    // 左右指针，从s[l]和s[r]向两边扩散，找到最长回文串
    while (l >= 0 && r < s.length && s[l] == s[r]) {
        l--; r++;
    }
    return s.substr(l + 1, r - l - 1);
}

⭐️⭐️Manacher算法