x 5. Longest Palindromic Substring

5. Longest Palindromic Substring

https://m.blog.naver.com/jqkt15/222108415284

https://www.crocus.co.kr/1075

With Manacher’s Algorithm

time: O(n)

space: O(n)

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
    let newS = '#';
    for (const c of s) {
        newS += c + '#';
    }

    let max = 0;
    let idx = 0;

    const P = new Array(newS.length).fill(0);
    let r = 0;
    let c = 0;
    for (let i = 0; i < newS.length; i++) {
        if (r < i) {
            P[i] = 0;
        } else if (r >= i) {
            P[i] = Math.min(P[2 * c - i], r - i);
        }

        while (i - P[i] - 1 >= 0 && i + P[i] + 1 < newS.length && newS[i - P[i] - 1] === newS[i + P[i] + 1]) {
            P[i]++;
        }

        if (r < i + P[i]) {
            r = i + P[i];
            c = i;

            if (max < P[i]) {
                max = P[i];
                idx = i;
            }
        }
    }

    return newS.substring(idx - max, idx + max + 1).replace(/#/g, '');
};

time: O(n^2)

space: O(1) ⇒ O(n) if substring counted

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let max = [0, 1];

    for (let i = 0; i < s.length - 1; i++) {
        const odd = checkPalindrome(s, i, i);
        const even = checkPalindrome(s, i, i + 1);

        let localMax = odd;
        if (odd[1] - odd[0] < even[1] - even[0]) {
            localMax = even;
        }

        if (max[1] - max[0] < localMax[1] - localMax[0]) {
            max = localMax;
        }

    }

    return s.substring(max[0], max[1]);
};

function checkPalindrome(str, s, e) {

    while (s >= 0 && e < str.length) {
        if (str[s] !== str[e]) {
            break;
        }
        s--;
        e++;
    }

    return [s + 1, e];
}