Longest Palindromic Subsequence

Statement

Given a string, find the length of the longest palindromic subsequence if it exists. In a palindromic subsequence, elements read the same backward and forward.

A subsequence is a sequence that can be derived from another sequence by deleting or keeping some elements without changing the order of the remaining elements.

Let’s say that we are given a string “abbca” to find its longest palindromic subsequence. We see in this example that if we ignore “c” in the given string, we get the longest palindrome (“abba”) of this sequence which has a length of $4$.

Constraints:

• s consists of lowercase letters.

• $1 \leq$ s.length $\leq 5000$