Problem Statement
Longest Palindromic Subsequence
You are given a string s. Your job is to find the longest palindrome you can build by keeping some of its letters in their original order. A palindrome is a word that reads the same forwards and backwards, like "bbbb" or "aba". A subsequence means you are allowed to delete letters but you cannot rearrange them. So from "bbbab" you could delete the "a" and keep "bbbb", which reads the same both ways and has length 4. We want the length of the longest one. The tool for this is a table that remembers answers to smaller pieces so we never solve the same piece twice. We will build a 2D table dp where dp[i][j] holds the answer for just the slice of the string from position i to position j.
Signals to notice
Brute force first
Generate all subsequences and check which are palindromes. Exponential. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
The LPS of string s equals the LCS of s and reverse(s). Use the standard LCS DP. Alternatively, interval DP: dp[i][j] = LPS length of s[i.j]. If s[i]==s[j], dp[i][j] = dp[i+1][j-1] + 2. Else max(dp[i+1][j], dp[i][j-1]). Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on s="bbbab" (indices: b0 b1 b2 a3 b4)
init: dp[i][i]=1 for all i -> diagonal all 1s, n=5
len=2: dp[0][1] s[0]=b==s[1]=b -> dp[1][0... ](empty)=0 +2 =2; dp[1][2] b==b ->2; dp[2][3] b!=a ->max(1,1)=1; dp[3][4] a!=b ->max(1,1)=1
len=3: dp[0][2] b==b -> dp[1][1]+2 =1+2=3; dp[1][3] b!=a ->max(dp[2][3]=1,dp[1][2]=2)=2; dp[2][4] b==b -> dp[3][3]+2 =1+2=3
len=4: dp[0][3] s0=b!=s3=a ->max(dp[1][3]=2,dp[0][2]=3)=3; dp[1][4] s1=b==s4=b -> dp[2][3]+2 =1+2=3
len=5: dp[0][4] s[0]=b==s[4]=b -> dp[1][3]+2 =2+2=4
return dp[0][4] = 4 ("bbbb")What must stay true
A palindrome reads the same forwards and backwards. The longest palindromic subsequence is equivalent to the longest common subsequence between the string and its reverse — characters that appear in matching order from both ends. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
dp[i][i] = 1 for all i
for length in 2..n:
for i in 0..n-length:
j = i + length - 1
if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Confusing palindromic SUBSEQUENCE with palindromic SUBSTRING — subsequences don't need to be contiguous. The DP allows skipping characters. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.