Longest Palindromic Subsequence

A subsequence of a string keeps some of its characters, in their original order, and drops the rest: "cat" is a subsequence of "chart", but "tac" is not. A palindrome reads the same forwards and backwards.

Write longest_palindrome_subseq(s) that returns the length of the longest subsequence of s that is a palindrome.

Examples

longest_palindrome_subseq("character")  # returns 5
longest_palindrome_subseq("banana")     # returns 5
longest_palindrome_subseq("abcd")       # returns 1

In "character" you can keep "carac". In "abcd" no two letters match, so the best is a single letter.

Constraints

• 1 <= len(s) <= 500
• s holds lowercase letters only.