Longest Palindromic Subsequence
You get a string s made of lowercase English letters.
A subsequence is what is left after you delete zero or more characters. The characters that stay keep their original order. They do not need to be next to each other.
A palindrome reads the same from left to right and from right to left.
Return the length of the longest subsequence of s that is a palindrome.
Hint
Let best(i, j) be the answer for the part of s from index i to index j. If s[i] equals s[j], both ends can be used together. If they are different, at least one end must be dropped. Fill the table for short parts first.
Examples
Example 1
- Input:
- "carbonrace"
- Output:
- 7
Keep "carorac" (c, a, r, o, r, a, c). It reads the same both ways and has length 7.
Example 2
- Input:
- "xyz"
- Output:
- 1
All letters are different, so the best palindrome is a single letter.
Example 3
- Input:
- "abbcbba"
- Output:
- 7
The whole string is already a palindrome.
Constraints
1 <= s.length <= 40shas only lowercase English letters.
Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.