Pattern visualizer

Longest Palindromic Subsequence

Look only at the two ends of the range s[i..j]. If they match, both letters belong to the outer shell of a palindrome, so the answer for [i, j] is 2 plus the answer for the interior [i+1, j-1]. If they don't match, the best palindrome can't use both ends, so it lives entirely inside [i+1, j] or [i, j-1] — take whichever is longer. Filling the table from the bottom row up (i decreasing) and left to right guarantees dp[i+1][*] and dp[i][j-1] are already known whenever a cell is written. Animated on: s = "bbbab" — find the length of the longest subsequence of s that reads the same forwards and backwards..

dp[i][j] = dp[i+1][j-1] + 2 when s[i] = s[j], else MAX(dp[i+1][j], dp[i][j-1])

time O(n^2)space O(n^2)step 1 / 16

dp[i][j] = longest palindromic subsequence of s[i..j], s = "bbbab"

bbbab

line 4

A single character s[4] = 'b' is a palindrome by itself: dp[4][4] = 1.

Pseudocode

1FUNCTION longestPalinSubseq(s):
2  n <- LENGTH(s)
3  FOR i FROM n-1 DOWNTO 0:
4    dp[i][i] <- 1
5    FOR j FROM i+1 TO n-1:
6      IF s[i] = s[j]:
7        dp[i][j] <- dp[i+1][j-1] + 2
8      ELSE:
9        dp[i][j] <- MAX(dp[i+1][j], dp[i][j-1])
10  RETURN dp[0][n-1]

← / → step · space play · Home restart

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap