LongestPalindromicSubsequence.js

/*
 LeetCode -> https://leetcode.com/problems/longest-palindromic-subsequence/

 Given a string s, find the longest palindromic subsequence's length in s.
 You may assume that the maximum length of s is 1000.

*/

export const longestPalindromeSubsequence = function (s) {
 const n = s.length

 const dp = new Array(n)
 .fill(0)
 .map((item) => new Array(n).fill(0).map((item) => 0))

 // fill predefined for single character
 for (let i = 0; i < n; i++) {
 dp[i][i] = 1
 }

 for (let i = 1; i < n; i++) {
 for (let j = 0; j < n - i; j++) {
 const col = j + i
 if (s[j] === s[col]) {
 dp[j][col] = 2 + dp[j + 1][col - 1]
 } else {
 dp[j][col] = Math.max(dp[j][col - 1], dp[j + 1][col])
 }
 }
 }

 return dp[0][n - 1]
}