0005. Longest Palindromic Substring.md

Given a string s, return the longest palindromic substring in s.

Time complexity : O(n^2). Since expanding a palindrome around its center could take O(n) time, the overall complexity is O(n^2). Space complexity : O(1)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res = "";
    
    for(let i = 0; i < s.length; i++) {
        let type1 = findLongestPalindrome(s, i, i);
        let type2 = findLongestPalindrome(s, i, i + 1);
        // find which string has the longest length, then take that string as longest
        let longest = type1.length > type2.length ? type1 : type2;
        
        if(res.length < longest.length) {
            res = longest;
        }
    }
    return res;
};

let findLongestPalindrome = function(str, i, j) {
    while(i >= 0 && j < str.length && str[i] === str[j]) {
        i--;
        j++;
    }
    // we have i-- and j++ in the while loop, so here we need i + 1 and j
    return str.slice(i + 1, j);
}