DSA Tracker

Visualize

Longest Palindromic Subsequence

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)

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.

Details

Animated on: s = "bbbab" — find the length of the longest subsequence of s that reads the same forwards and backwards.

Problem:Longest Palindromic SubsequenceMedium

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

step 1 / 16

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

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

Every step in words

Show all 16 steps
  1. A single character s[4] = 'b' is a palindrome by itself: dp[4][4] = 1.
  2. A single character s[3] = 'a' is a palindrome by itself: dp[3][3] = 1.
  3. s[3]='a' != s[4]='b', so one end can be dropped: dp[3][4] = MAX(dp[4][4]=1, dp[3][3]=1) = 1.
  4. A single character s[2] = 'b' is a palindrome by itself: dp[2][2] = 1.
  5. s[2]='b' != s[3]='a', so one end can be dropped: dp[2][3] = MAX(dp[3][3]=1, dp[2][2]=1) = 1.
  6. s[2]='b' matches s[4]='b', so both sit in the outer shell of a palindrome: dp[2][4] = 2 + (dp[3][3] = 1) = 3.
  7. A single character s[1] = 'b' is a palindrome by itself: dp[1][1] = 1.
  8. s[1]='b' matches s[2]='b', so both sit in the outer shell of a palindrome: dp[1][2] = 2 + (the interior is empty (length 0)) = 2.
  9. s[1]='b' != s[3]='a', so one end can be dropped: dp[1][3] = MAX(dp[2][3]=1, dp[1][2]=2) = 2.
  10. s[1]='b' matches s[4]='b', so both sit in the outer shell of a palindrome: dp[1][4] = 2 + (dp[2][3] = 1) = 3.
  11. A single character s[0] = 'b' is a palindrome by itself: dp[0][0] = 1.
  12. s[0]='b' matches s[1]='b', so both sit in the outer shell of a palindrome: dp[0][1] = 2 + (the interior is empty (length 0)) = 2.
  13. s[0]='b' matches s[2]='b', so both sit in the outer shell of a palindrome: dp[0][2] = 2 + (dp[1][1] = 1) = 3.
  14. s[0]='b' != s[3]='a', so one end can be dropped: dp[0][3] = MAX(dp[1][3]=2, dp[0][2]=3) = 3.
  15. s[0]='b' matches s[4]='b', so both sit in the outer shell of a palindrome: dp[0][4] = 2 + (dp[1][3] = 2) = 4.
  16. dp[0][4] = 4 — the whole string "bbbab" has a longest palindromic subsequence of length 4.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Palindromic Subsequence in the editorAll Dynamic Programming problemsBack to roadmap