Count the number of palindromic subsequences in a given string
Given a string you have to count the total number of palindromic subsequences in the giving string and print the value.
Input:
T Test case
T no of input string will be given to you.
E.g.
3
abc
aa
abcc
Constrain
1≤ length (string) ≤100
Output:
Print the count of the palindromic sub sequences from the given string.
Example
T=3
Input:
abc
Output:
3 ("a", "b", "c")
Input:
aa
Output:
3 ("a", "a", "aa")
Input:
abcc
Output:
5 ("a", "b", "c", "c", "cc")
f(a,b)=f(a+1,b)+f(a,b-1)+1
f(a,b)=f(a+1,b)+f(a,b-1)-f(a+1,b-1)
For, str = abbaa
From the above, it is understandable that one function is called repeatedly so for the large input the repetition will be very high. Because of this problem we are using a Dynamic programming approach to avoid repetition. We are using the memorization process to solve the problem.
Problem solution:
Recursive algorithm:
DP conversion:
C++ Implementation:
Output