Longest Palindromic Subsequence
Medium · Dynamic Programming · String · Dynamic Programming
Problem
Given a string s, return the length of its longest palindromic subsequence.
A subsequence is what is left after deleting zero or more characters without reordering the rest, so the kept characters do not have to be next to each other. A palindrome reads the same forwards and backwards.
Examples
Input: s = "character" Output: 5
"carac" is a palindromic subsequence of length 5, and none is longer.
Input: s = "abcd" Output: 1
All characters differ, so the best is any single character.
Input: s = "aabaa" Output: 5
The whole string is already a palindrome.
Constraints
- 1 <= len(s) <= 1000
- s consists only of lowercase English letters.
Approaches
- Baseline: recursion on the two ends, memoized — time O(n²), space O(n²)
Follow-up
The same table answers related questions: the fewest insertions to make s a palindrome is len(s) minus this answer, and whether k deletions are enough compares it with len(s) - k. Both are the use cases below. A palindromic substring (contiguous) is a different problem, solved by expanding around centers.
Related problems
Start free on Cariara · Coding problems · System design studio
