mediumDynamic programming, 2D target 25 min
Longest palindromic subsequence
You get a string s of lowercase letters. A subsequence keeps some of the letters in their original order and drops the rest. A palindrome reads the same forward and backward, like "level".
Return the length of the longest subsequence of s that is a palindrome.
Example 1
Input
s = "agbcba"Output5Dropping the g leaves "abcba".
Example 2
Input
s = "abcd"Output1No letter repeats, so the best palindrome is a single letter.
Example 3
Input
s = "character"Output5One answer is "carac", from the letters at positions 0, 2, 3, 4 and 5.
Constraints
1 ≤ len(s) ≤ 1,000
sholds only lowercase English letters.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.