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 44.

Constraints:

  • s consists of lowercase letters.

  • 11 \leq s.length 5000\leq 5000

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.