Is it solvable with DP in JavaScript?


  • 0
    S

    After struggling for long, I gave up and looked at the solution and implemented Approach #1. However, I am still failing the last test case due to "time limit exceeded" (the string "aaa...aaa" with a thousand a's). Am I doing anything wrong with my implementation? Thanks in advance for any help!

    var longestPalindrome = function(s) {    
        var reversed = s.split('').reverse().join('');
        var max = 0; // store max length of palindrome string
        var max_s = ""; // store longest palindrome string
        
        var arr = [];
        for(var i=0; i<s.length; i++){ // initalize 2d array
            arr.push(new Array(s.length));
        }
        
        for(var i=0; i<s.length; i++){
            for(var j=0; j<reversed.length; j++){
                if(s[i]===reversed[j]){
                    if(i===0 || j===0){
                        arr[i][j] = 1;
                        if(max===0){
                            max_s = s[0];
                        }
                    } else {
                        arr[i][j] = arr[i-1][j-1] + 1;
                        if(arr[i][j] > max){
                            // check for valid indices as explained in the solution
                            var first = [i-arr[i][j]+1, i]; // indices of the palindrome in the original string
                            var second = [j-arr[i][j]+1, j]; // indices of the palindrome in the reversed string
                            if(s.length - first[0] - 1 === second[1] && s.length - first[1] - 1 === second[0]){
                                max = arr[i][j]; // update variables when a valid  and longer palindrome is found
                                max_s = s.substring(i-max+1, i+1);
                            }
                        }
                    }
                } else {
                    arr[i][j] = 0;
                }
            }
        }
        return max_s;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.