Longest Palindromic Subsequence
Problem
Return the length of the longest subsequence (not necessarily contiguous) that is a palindrome.
Example 1
Input: "bbbab" Output: 4
"bbbb".
Example 2
Input: "cbbd" Output: 2
Also asked as: Longest Palindromic Subsequence
Test cases
Case 1
Input: "bbbab" Expected: 4
Case 2
Input: "cbbd" Expected: 2
Case 3
Input: "abc" Expected: 1
Case 4
Input: "a" Expected: 1
View solutionHide solution1 approach
1. LCS of the string and its reverse
Time O(n²)Space O(n²)
The longest subsequence that reads the same forwards and backwards is exactly the LCS of s and reverse(s).
function longestPalindromeSubseq(s) { const r = [...s].reverse().join(''); const n = s.length; const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0)); for (let i = 1; i <= n; i++) for (let j = 1; j <= n; j++) dp[i][j] = s[i - 1] === r[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]); return dp[n][n];}Direct interval DP also works: dp[i][j] = 2 + dp[i+1][j-1] if s[i]===s[j], else max(dp[i+1][j], dp[i][j-1]).