← Back

🏰 Palindrome Castle

Find Longest Palindromic Subsequence • LPS = LCS(s, reverse(s))

🪞 String vs Reverse (Mirror)

📊 LCS Table (s vs reverse(s))

📐 LPS = LCS Trick!

LPS(s) = LCS(s, reverse(s))
The longest palindromic subsequence
is the same forwards and backwards!
String Length
-
Min Deletions
-
LPS Length
?

💡 Key Insight

Min deletions to make palindrome:
= n - LPS(s)

Because LPS characters stay,
rest need to be deleted!