Given a string "s" of length "n", the task is to find the total number of palindromic subsequences present in it.
Note that the empty string is not considered a palindrome.
Input: abcd
Output: 4
Input: aab
Output: 4
Solutions
Method 1: DP (Memoization)
We can solve this problem with recursion or memoization (DP).
The idea is to keep two pointers, "i" and "j", pointing to the start and end position of the string.
In each recur, if corner characters are equal, that means it will have this whole string as a palindrome, so add 1, also add the recursive result for including and excluding ith and jth characters.
If the corner characters are not equal, the current string is not a palindrome, so add nothing. Also, remove duplicate entries by subtracting palindromic subsequences of the middle string (i+1..j-q).
Complexity
The time complexity of this solution is O(n*n) and space complexity is O(n*n).