394. Longest Palindromic Subsequence
You are given a string s of lowercase English letters. A subsequence keeps the original left-to-right order of characters but may drop any of them; it does not have to be contiguous.
Among all subsequences of s that read the same forwards and backwards, return the length of the longest one as a single integer.
For instance, "agbdba" contains the palindromic subsequence "abdba" (drop the g), so its answer is 5.
Example 1:
Input: s = "agbdba"
Output: 5
Explanation: Deleting the g leaves "abdba", which is a palindrome of length 5. No palindromic subsequence of length 6 exists.
Example 2:
Input: s = "xyz"
Output: 1
Explanation: No two characters match, so the best palindrome is any single character.
Constraints:
- 1 ≤ s.length ≤ 1000
- s consists of lowercase English letters only
Hints:
A palindrome is decided at its two ends. Look at the first and last characters of the current slice: if they are equal, both can be kept in the answer.
Define lps(i, j) = the answer for the slice s[i..j]. If s[i] == s[j], it is 2 + lps(i+1, j-1); otherwise it is max(lps(i+1, j), lps(i, j-1)). Memoize, or fill a table from short slices to long ones.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "agbdba"
Expected output: 5