Longest palindromic substring - javascript TLE


  • 0
    A

    The following is the dynamic programming solution that runs in O(n^2) time. Any idea why it encounters Time Limit Exceeded?

    var longestPalindrome = function(s) {
        // let table = initialiseTable()
        let table = {}
        let longest = s.length > 0? s[0] : ""
        for(let i=0; i< s.length; i++){
            table[`${i},${i}`]= true
        }
        for(let i=0; i< s.length-1; i++){
            if(s[i]===s[i+1]){
                table[`${i},${i+1}`]= true
                longest = s.substring(i,i+1 + 1)
            }
        }
        for(let len=3; len <= s.length; len ++){
            for(let i= 0; i<= s.length - len; i++){
                let j = len + i - 1
                if(s[i]===s[j] && table[`${i+1},${j-1}`]){
                    table[`${i},${j}`] = true
                    longest = s.substring(i,j+1)
                }
            }
        }
        return longest
    };
    

  • 0
    V

    Rather than keeping track of the longest substring, you could just keep track of the indices. That way you will only need one substring call at the end of the function.


Log in to reply
 

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