题解 | #最长回文子串#

中心扩散法

当字符串只有一个字符时，这个字符串必然为回文串。中心扩散法将字符串中的每个字符作为中心，看这个字符串左右两边的字符是否相等，如果相等说明这两个字符和该字符组成的子串也是回文串，则更新这个字符所能组成的回文子串的最大长度，并继续向左右外扩一个字符，直到这两个字符不相等为止。

但是中心扩散的方法处理奇数长度的字符串比较方便，可以用一个原字符串中不存在的字符，插在原字符串中的每个字符中间，构造一个新的字符串，假设原字符串的字符个数为n，插入的字符个数必然为n+1，则新字符串的长度为n+n+1=2n+1，这样无论之前的字符串是奇数长度还是偶数长度，都能构造出一个奇数长度的字符串。

中心扩散的逻辑需要遍历每个字符为中间字符，关键要有中间字符的左边字符索引和右边字符的索引，不断更新这两个索引实现外扩，因此时间复杂度达到O(n²)。此外需要在遍历过程中需要更新整个字符串的最大回文子串长度，因此需要一个变量保存最大回文子串长度，空间复杂度为O(1)。

注意处理过的新字符串的每个字符的回文子串长度要恢复成原字符串的回文子串长度，假设某个字符是新插入的字符，他的回文半径为n（半径包括该字符），则除去该字符后的右边子串长度为n-1，n-1中有一半是新加入的字符，所以n-1中原字符串中的字符为(n-1)/2，该字符后的左边子串中原字符串中的字符数量也为(n-1)/2，两边加起来得到原字符串中的字符数量为(n-1)/2+(n-1)/2=n-1。假设某个字符是原字符串中的字符，他的回文半径为n，去除该字符后得到的右边子串长度为n-1，此时的n-1中新插入的字符比原字符串中的字符多一个，所以原字符串中的字符个数为(n-1-1)/2，同理左边子串中原字符串中的字符数量也为(n-1-1)/2，两者相加再加上中间的原字符串的字符就得到了回文串中原字符串中的字符数量为(n-1-1)/2+(n-1-1)/2+1=n-1。综上，该字符在原字符串中的回文串长度为新字符串的回文半径-1。

参考：

https://blog.nowcoder.net/n/2e17655351a74889af0af70741396e49?f=comment

https://www.bilibili.com/video/BV1Ug411F7wD?spm_id_from=333.880.my_history.page.click

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param A string字符串
 * @return int整型
 */
function getLongestPalindrome( A ) {
    // write code here
    const oddStr = [...A].map(c => "#"+c).concat(["#"]).join("");  // 将字符串预处理成拥有奇数个字符的字符串
    let maxSubLength = 1;

    
    for (let i = 1; i < oddStr.length-1; ++i) {
        let l = i - 1;
        let r = i + 1;
        let radius = 1;  // 每个字符的最小回文子串都是当前字符，因此最小半径是1
        while (l >=0 && r < oddStr.length && oddStr[r] === oddStr[l]) {  // 用while循环处理中心扩散的逻辑，需要l和r两个变量
            --l;
            ++r;
            radius += 1;
        }
        maxSubLength = Math.max(radius-1, maxSubLength);  // radius-1为原始未经过预处理时的当前字符的最长回文子串长度
    }

    return maxSubLength;
}
module.exports = {
    getLongestPalindrome: getLongestPalindrome,
};

动态规划法

回文串的特性

• 如果一个字符串是回文串，则这个字符串两边增加相同的字符时也是回文串，如果两边增加不同的字符后的新字符串不是回文串。
• 因此判断一个字符串是否为回文串，可以从这个字符串首尾两端的字符入手，由外往内内缩字符，只要首尾两个字符不相同必然不是回文串。如果两边的字符相同，再判断中间的字符串是否为回文串。

DP数组应该存放什么？

对于字符串最值问题一般要构建二维DP表，此处的dp[i][j]表示的是该字符串中从j到i的子串是否为回文串，如果是回文串，则更新最大回文串长度为j-i+1。

最小子问题

• 当一个字符串只有一个字符时也是回文串，此时回文串长度为1。
• 当一个字符串首尾字符相同，且字符串长度小于4时一定是回文串。

状态转移方程

• 如果dp[i][j]表示的子串的两边字符不相等，则这个子串不是回文串，dp[i][j] = false。
• 如果dp[i][j]表示的子串的两边字符相等，则这个子串如果长度小于4就是回文串，直接更新dp[i][j] = true。
• 如果dp[i][j]表示的子串的两边字符相等，则这个子串如果长度大于等于4，则这个子串是否为回文串取决于这个字符串左右两边内缩一个字符的子串，dp[i][j] = dp[i-1][j+1](j<=i)。

参考

https://blog.nowcoder.net/n/28cce3d4476c4d738ade38e0302a7c90?f=comment

https://blog.nowcoder.net/n/99462149a22d479ba9a3d5c8e7fd0247?f=comment

function getLongestPalindrome_DP( A ) {
    // write code here
    const dp = Array.from(new Array(A.length), () => new Array(A.length).fill(false));  // dp[i][j]判断从j到i的子串是否为回文子串
    let maxSubLength = 1;

    for (let i = 0; i < A.length; ++i) {  // i从0开始，后面有距离判断，不用担心i-1越界
        for (let j = 0; j <= i; ++j) {
            if (A[i] === A[j]) {  // 只有A[i] === A[j]时才有可能是回文串，A[i] !== A[j]则dp[i][j]为默认的false，不是回文串
                if (i-j+1 <= 3) {  // 判断回文串的最小逻辑：A[i] === A[j]且i和j之间的字符在0到3内，都是回文串
                    dp[i][j] = true;
                }
                else {  // i和j之间距离大于3进入这个分支，此时不用担心i-1和j+1会超过数组范围
                    dp[i][j] = dp[i-1][j+1];
                }
            }
            if (dp[i][j]) {
                maxSubLength = Math.max(maxSubLength, i-j+1);
            }
        }
    }

    return maxSubLength;
}

Manacher算法

• 将原字符串插入原字符串中不存在的字符，统一构造出奇数字符个数的新字符串。
• 遍历新字符串中的每个字符，用中心扩散法获取当前字符的最长回文串s，并更新当前取得的最长回文串的半径s_radius，当前最长回文串的中心字符的索引s_index以及当前最长回文串的最右字符的索引s_right。
• 如果遍历的字符索引i在当前最长回文串的最右索引s_right内，利用回文串的特性，取得当前字符关于s_index对称的索引j的最长回文串半径，j在i前面，所以他的回文串半径已经求出来了，j的回文串肯定在s内，而i的回文串在s内的部分的长度跟j相同，超过s的部分就需要继续用中心扩散法求最长回文串。
• 如果求出的最长回文串长度超过了目前的最长回文串长度，就需要更新当前最长回文串的半径，中心字符的索引还有最右字符的索引。

参考

https://www.bilibili.com/video/BV1Ug411F7wD?spm_id_from=333.880.my_history.page.click

function getLongestPalindrome_Manacher( A ) {
    // write code here
    const oddStr = [...A].map(c => "#"+c).concat(["#"]).join("");  // 将字符串预处理成拥有奇数个字符的字符串
    const dp = new Array(oddStr.length).fill(1);  // 存放新字符串每个字符的最大回文半径
    let maxSubRadius = 1;  
    let currentMaxIndex = 0;  // 存放目前最长回文串的中心字符的索引
    let currentMaxRight = 0;  // 存放目前最长回文串的最右字符的索引

    
    for (let i = 1; i < oddStr.length; ++i) {
        if (currentMaxRight > i) {  // i刚好等于currentMaxRight时，即当前字符在目前最长回文串的最右索引时，也需要中心扩散法更新dp[i]
            dp[i] = Math.min(dp[2*currentMaxIndex-i], currentMaxRight-i);  // i目前最长的回文串内，所以i左右扩展在最长回文串内的子串也是回文串，超出部分用中心扩散法继续判断是否为回文串
        }

        let l = i - dp[i];  // dp[i]存放目前以i为中心的最大回文串的半径
        let r = i + dp[i];
        while (l >=0 && r < oddStr.length && oddStr[r] === oddStr[l]) {  // 用while循环处理中心扩散的逻辑，需要l和r两个变量
            --l;
            ++r;
            dp[i] += 1;  
        }
        if (maxSubRadius < dp[i]) {  // 此时i的最大回文半径超过了目前的最大回文半径
            maxSubRadius = dp[i];
            currentMaxIndex = i;
            currentMaxRight = r-1;
        }
    }

    return maxSubRadius-1;
}