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) {
  if (typeof s !== 'string') {
    throw new TypeError('Input must be a string')
  }

  const n = s.length

  if (n === 0) {
    return 0
  }

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

  // single character palindromes
  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]
}