Count total number of Palindromic Subsequences
Given a string str, find total number of possible palindromic sub-sequences. A sub-sequence does not need to be consecutive, but for any xixj i<j must be valid in the parent string too. Like "icl" is a subsequence of "includehelp" while "ple" is not.
Input:
The first line of input contains an integer T, denoting the no of test cases then T test cases follow. Each test case contains a string str.
Output:
For each test case output will be an integer denoting the total count of palindromic subsequence which could be formed from the string str.
Constraints:
1 <= T <= 100
1 <= length of string str <= 300
Example:
Input:
Test case: 2
First test case:
Input string:
"aaaa"
Output:
Total count of palindromic subsequences is: 15
Second test case:
Input string:
"abaaba"
Output:
Total count of palindromic subsequences is: 31
Explanation:
Test case 1:
Input: "aaaa"
The valid palindromic subsequences are shown below,
Marked cells are character taken in subsequence:
Count=1
Count=2
Count=3
Count=4
Count=5
Count=6
Count=7
Count=8
Count=9
Count=10
Count=11
So on...
Total 15 palindromic sub-sequences
Actually in this case since all the character is same each and every subsequence is palindrome here.
For the second test case
Few sub-sequences can be
"a"
"b"
"a"
"aba"
So on
Total 31 such palindromic subsequences
This can be solved by using DP bottom up approach,
To understand this lets think of a string like "acaa"
Here dp[0][1]=2 because there's only two palindrome possible because of "a" and "c".
Whereas for dp[2][3] value will be 3 as possible subsequences are "a", "a", "aa".
So for higher lengths if starting and ending index is the same then we recur for the remaining characters, since we have the sub-problem result stored so we computed that. In case start and end index character are different then we have added dp[start+1][end] and dp[start][end-1] that's similar to recur for leaving starting index and recur for leaving end index. But it would compute dp[start+1][end-1] twice and that why we have deducted that.
For proper understanding you can compute the table by hand for the string "aaaa" to understand how it's working.
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer