5.最长的回文子串

/**
 * @param {string} s
 * @return {string}
 */
// 暴力枚举
var longestPalindrome = function (s) {
    let res = []
    // 自身单个字符也算一个回文串，假设没有长度大于1的回文串，则每个字符都是一个回文串，长度为1
    let maxLenStr = s.charAt(0)

    // 枚举以每个字母开头的回文串
    for (let i = 0; i < s.length; i++) {
        start = i
        // 从后往前遍历找回文串,从后往前这样才能找到更长的回文串
        for (let j = s.length - 1; j > start; j--) {
            let start = i // 开头下标
            let end = j // 结尾下标
            // 检查是否符合回文串
            let isHuiWen = true
            while (start < end) {
                if (s.charAt(start) !== s.charAt(end)) {
                    isHuiWen = false
                    break
                }
                start++
                end--
            }
            if (isHuiWen) {
                let str = s.substring(i, j + 1)
                res.push(str)
                if (str.length > maxLenStr.length) {
                    maxLenStr = str
                }
            }
        }
    }
    console.log(res)
    return maxLenStr
};

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    let maxStr = ''
    // 中心扩散法找回文串
    // 遍历每个字符，以每个字符为中心，向左右扩散找回文串
    for (let i = 0; i < s.length; i++) {
        let char = s.charAt(i) // 以char为中心向左右扩散找回文串
        // 回文串有两种形式
        let str1 = expandAroudCenter(s, i, i) // 中间含有单个字符：aabcc,左右起点都是b
        let str2 = expandAroudCenter(s, i, i + 1) // 中间不含单个字符: aabbcc,左起点是第一个b，右起点是第二个b
        // 比较str1,str2,maxStr的长度
        let max = str1.length > str2.length ? str1 : str2
        maxStr = max.length > maxStr.length ? max : maxStr
    }
    return maxStr
}

function expandAroudCenter(s, left, right) {
    while (left >= 0 && right < s.length && s.charAt(left) === s.charAt(right)) {
        left--
        right++
    }
    let strStart = left + 1 // while最后多减了一次，要加回来
    let strEnd = right - 1 // while最后多加了一次，要减回去
    let str = s.substring(strStart, strEnd + 1)
    return str
}

// console.log(longestPalindrome("babad"))
console.log(longestPalindrome("aacabdkacaa"))