5. Longest Palindromic Substring

/**
 * @param {string} s
 * @return {string}
 */
 /**
 time: O(n^3)
 space: O(n)
*/
var longestPalindrome = function(s) {
    let max = s[0];

    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            if (isPalindrome(s, i, j)) {
                if (j - i + 1 >= max.length) {
                    max = s.substring(i, j + 1);
                }
            }
        }
    }

    return max;
};

function isPalindrome(str, s, e) {
    while (s <= e) {
        if (str[s] !== str[e]) {
            return false;
        }
        s++;
        e--;
    }

    return true;
}

/**
time: O(n^2)
space: O(n)
 */
var longestPalindrome = function(s) {
    let max = [0, 1];

    for (let i = 0; i < s.length - 1; i++) {
        const odd = getLongest(s, i, i);
        const even = getLongest(s, i, i + 1);
        
        // find longest btw odd and even
        let current = even;
        if (odd[1] - odd[0] >= even[1] - even[0]) {
            current = odd;
        }

        // find longest btw current and current max
        if (current[1] - current[0] > max[1] - max[0]) {
            max = current;
        }
    }
    
    return s.slice(max[0], max[1]);
};

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

    return [s + 1, e];
}