# 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,

dp[n][n]where n be the string length to 0dp[i][i+1]=3, else if characters are different thendp[i][i+1]=2To understand this lets think of a string like "acaa"

Here

dp[0][1]=2because 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".dp[0][n-1];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

startandendindex character are different then we have addeddp[start+1][end]anddp[start][end-1]that's similar to recur for leaving starting index and recur for leaving end index. But it would computedp[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:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: