NC17 最长回文子串

https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af (opens new window)

描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

示例1

输入：
"ababc"

返回值：
3

说明：
最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入：
"abbba"

返回值：
5

示例3

输入：
"b"

返回值：
1

解答

以每个字符为中心点，从两边查找，判断左右是否相等，找到最大长度的子串

分两种情况：1. abc; 2. abbc。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A string字符串 
 * @return int整型
 */
function getLongestPalindrome( A ) {
    const str = A;
    const len = str.length;

    if (len <= 1) {
        return len;
    }

    let max = 0;

    for (let i = 0; i < len; i++) {
        max = Math.max(max, helper(str, i, i), helper(str, i, i + 1));
    }

    return max;
}

function helper(str, left, right) {
    const len = str.length;

    while (left >= 0 && right < len) {
        if (str[left] === str[right]) {
            left -= 1;
            right += 1;
        } else {
            break;
        }
    }

    return right - left + 1 - 2;
}


module.exports = {
    getLongestPalindrome : getLongestPalindrome
};