Write longest_palindrome_subseq(s: str) -> int: the length of the longest subsequence of s (characters kept in order, gaps allowed) that is a palindrome.
Examples:
longest_palindrome_subseq("character") == 5("carac")longest_palindrome_subseq("abcd") == 1longest_palindrome_subseq("aabaa") == 5
Constraints: 1 <= len(s) <= 600, lowercase letters. Trying subsequences is exponential; aim for O(n²).
Show hint
think about the answer for every substring s[i..j], built up from shorter ones. What can you do when its two end characters match, and what when they don't?