Longest Palindromic Subsequence
Let's solve the Longest Palindromic Subsequence problem using Dynamic Programming.
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$
Level up your interview prep. Join Educative to access 70+ handson prep courses.