Dynamic Programming • Strings

Longest Palindromic Subsequence

Find the length of the longest palindromic subsequence in a string by evaluating shrinking boundaries.

Overview

A palindrome reads the same forwards and backwards. We use DP to find the longest subsequence that forms a palindrome.

The State

`dp[i][j]` represents the length of the longest palindromic subsequence in the substring `s[i...j]`.

Match Case

If the boundary characters match (`s[i] == s[j]`), they contribute 2 to the length, plus whatever the longest palindrome is strictly inside them: `2 + dp[i+1][j-1]`.

Mismatch Case

If they don't match, the longest palindrome must ignore one of the boundaries. It's the max of ignoring `s[i]` or ignoring `s[j]`: `max(dp[i+1][j], dp[i][j-1])`.

i \ j	0 (b)	1 (b)	2 (b)	3 (a)	4 (b)
0 (b)	0	0	0	0	0
1 (b)	0	0	0	0	0
2 (b)	0	0	0	0	0
3 (a)	0	0	0	0	0
4 (b)	0	0	0	0	0

Code Tracker

:::

1let dp = Array(n).fill().map(() => Array(n).fill(0));

2for (let i = 0; i < n; i++) dp[i][i] = 1;

3for (let len = 2; len <= n; len++) {

4 for (let i = 0; i <= n - len; i++) {

5 let j = i + len - 1;

6 if (s[i] === s[j] && len === 2) dp[i][j] = 2;

7 else if (s[i] === s[j]) dp[i][j] = dp[i+1][j-1] + 2;

8 else dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);

9 }

10}

11return dp[0][n-1];