Longest Palindromic Subsequence
Medium · dynamic programming
A subsequence of a string is what you get by deleting zero or more characters without changing the order of the rest. A palindrome reads the same forwards and backwards.
Given a string s, return the length of the longest subsequence of s that is a palindrome. The characters do not need to sit next to each other in s.
A single character is a palindrome, so the answer is always at least 1.
Examples
Example 1
Input: s = "character"
Output: 5
Keep the letters at positions 0, 2, 3, 4 and 5 to get "carac". No longer palindrome can be formed.
Example 2
Input: s = "abcd"
Output: 1
All four letters are different, so only a single letter is a palindrome.
Example 3
Input: s = "racecar"
Output: 7
The whole string already reads the same both ways.
Constraints
- 1 <= len(s) <= 1000
- s contains only lowercase English letters.