Longest Palindromic Subsequence

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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]).