DEV Community

loading...

LeetCode 516. Longest Palindromic Subsequence (javascript solution)

codingpineapple
・1 min read

Description:

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n^2)

var longestPalindromeSubseq = function(s) {
    const dp = [...Array(s.length)].map(() => Array(s.length).fill(0))

    // Base case 
    for(let i = 0; i < s.length; i++) {
        dp[i][i] = 1
    }

    for(let i = 1; i < s.length; i++) {
        for(let j = 0; j < s.length; j++){
            if(j+i < s.length){
                // If the end letter and start letter are the same add 2 to the value in the bottom left diagonal. This value is a potential palindrome. If the letters are not equal set the current value to the previous highest palindrome subsequence
                dp[j][j+i] = s[j] === s[j + i] 
                    ? dp[j+1][j+i-1] + 2
                    : Math.max(dp[j][j+i-1], dp[j+1][i+j])
            }
        }
    }

    return dp[0][s.length-1]
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)