Categories
interview

Longest Palindromic Substring

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(!s || s.length===0)
        return '';
    let start = 0, end = 0;
    for(let i = 0; i < s.length; i++) {
// There can be 2n - 1 centers for the palindromes. We can 
// include each character and the space in between the       
// characters.
        let l1 = expandAroundCenters(s, i, i);
        let l2 = expandAroundCenters(s, i, i + 1);
        let l = Math.max(l1, l2);
        if(l > end - start) {
           start = i - Math.floor((l - 1)/2);
           end = i + Math.floor(l/2);
        }
    }
    return s.substring(start, end + 1);
};

var expandAroundCenters = function(s, left, right) {
    while(left >= 0 && right < s.length && s.charAt(left) === s.charAt(right)) {
        left--;
        right++;
       }
   return right - left - 1;
}

// Time Complexity O(n ^ 2)
// Space Complexity O(1)