0005-longest-palindromic-substring.js

/**
 * Expand Around Center
 * Time O(N^2) | Space O(1)
 * https://leetcode.com/problems/longest-palindromic-substring/
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = (s) => {
    const isEmpty = s.length === 0;
    if (isEmpty) return '';

    const [left, right] = search(s); /* Time O(N * N) */

    return s.slice(
        left,
        right + 1,
    ); /* Time O(N * N) | Ignore Auxillary Space (N) */
};

const search = (s, left = 0, right = 0) => {
    for (let index = 0; index < s.length; index++) {
        /* Time O(N) */
        const len1 = getLength(s, index, index); /* Time O(N) */
        const len2 = getLength(s, index, index + 1); /* Time O(N) */
        const [length, window] = [Math.max(len1, len2), right - left];

        const canSkip = length <= window;
        if (canSkip) continue;

        left = index - ((length - 1) >> 1);
        right = index + (length >> 1);
    }

    return [left, right];
};

const getLength = (s, left, right) => {
    const canExpand = () => 0 <= left && right < s.length;
    const isSame = () => s[left] === s[right];

    const isPalindrome = () => canExpand() && isSame();
    while (isPalindrome()) {
        left--;
        right++;
    } /* Time O(N) */

    const window = right - left - 1;

    return window;
};