Given a string S, write a program to find the longest palindromic subsequence's length in S.

Problem Note

• What is Longest Palindromic Subsequence: A sequence that appears in the same relative order, but not necessarily contiguous(not substring) and palindrome in nature.

Example 1

Input: S = "aabcdebaz"
Output: 5
Explanation: "abcba" or "abdba" or "abeba" are longest Palindromic subsequence of length 5.There are many subsequences can be found which are palindrome like,"aa", "bcb", "aba", "bb" etc but we need to find the one with the maximum length.

Example 2

Input: S = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".