647. Palindromic Substrings

Manacher's Algorithm

1st try

time: O(n^2)

space: O(1)

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    
    let answer = 0;

    for (let i = 0; i < s.length; i++) {
        const odd = check(s, i, i);
        const even = check(s, i, i + 1);
        answer += odd + even;
    }

    return answer;
};

function check(str, s, e) {

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

    return cnt;
}