Given a String, find the longest palindromic subsequence.
Example 1:
Input:
S = "bbabcbcab"
Output: 7
Explanation: Subsequence "babcbab" is the
longest subsequence which is also a palindrome.
Example 2:
Input:
S = "abcd"
Output: 1
Explanation: "a", "b", "c" and "d" are
palindromic and all have a length 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestPalinSubseq() which takes the string S as input and returns an integer denoting the length of the longest palindromic subsequence of S.
Expected Time Complexity: O(|S||S|).
Expected Auxiliary Space: O(|S||S|).
Constraints:
1 ≤ |S| ≤ 1000

见题面

见题面