2019-05-16-longestPalindrome

• longestPalindrome

first trial:

// 09:07 - 09:56 think and code
// 10:00 - 10:38 debug succeed
// Runtime: 372 ms, faster than 31.08% of JavaScript online submissions for Longest Palindromic Substring.
// Memory Usage: 42.7 MB, less than 21.13% of JavaScript online submissions for Longest Palindromic Substring.

var longestPalindrome = function (s) {
    var sArr = s.split('');
    var max = { x: 0, y: 0, length: 0 };
    var map = {};

    for (var i = 0; i < sArr.length; i++) {
        var char = sArr[i];

        if (!map.hasOwnProperty(char)) {
            map[char] = [];
        }

        map[char].push(i);
    }

    for (var char in map) {
        var iArr = map[char];
        // bug iArr[iArr.length-1]-iArr[0] iLength miss check
        let iArrValueDiff = iArr[iArr.length-1]-iArr[0];
        
        if ( iArrValueDiff< max.length)
            // bug break 
            continue;
        
        var iLength = iArr.length;

        for (var p = 0; p < iLength; p++) {
            var pIndex = iArr[p];
            var maxQIndex = iArr[iLength - 1];
            
            if (maxQIndex - pIndex < max.length)
                break;
            
            for (var q = iLength - 1; q > p; q--) {
                var qIndex = iArr[q];

                if (qIndex - pIndex < max.length)
                    break;
                // contain left and right
                var subArr = sArr.slice(pIndex, qIndex + 1);

                processSubArr(subArr, max, pIndex, qIndex);
            }

            // bug babadada
        }
    }

    return sArr.slice(max.x, max.y+1).join('');
};

var processSubArr = function (arr, max, pIndex, qIndex) {
    var length = arr.length;

    if (length < max.length)
        return;

    if (isPalindromicArr(arr)) {
        max.length = length;
        max.x = pIndex;
        max.y = qIndex;
    }

    return;
};

var isPalindromicArr = function (arr) {
    var res = true;

    for (var i = 0, j = arr.length - 1; i < arr.length, j > i; i++, j--) {
        if (arr[i] !== arr[j]){
            res = false;
            break;
        }
    }

    return res;
};

// console.log(longestPalindrome("babad"));
// console.log(longestPalindrome("cbbd"));
// console.log(longestPalindrome("babadada"));
// console.log(longestPalindrome("222020221"));

Other solution

* @param {string} s
 * @return {string}
 */
function checkPalindrome(s, head, tail) {
    while (head >= 0 && tail < s.length && s.charAt(head) === s.charAt(tail)) {
        head--
        tail++
    }
    return s.slice(head+1, tail)
}

var longestPalindrome = function(s) {
    let max = ''
    for (let i = 0; i < s.length; i++) {
        let pal = checkPalindrome(s, i, i)
        let pal2 = checkPalindrome(s, i, i+1)
        if (pal.length > max.length) {
            max = pal
        }
        if (pal2.length > max.length) {
            max = pal2
        }
    }
    return max
};