# Count total number of Palindromic Substrings

Given a string **str**, find total number of possible palindromic sub-sequences. A substring need to be consecutive such that for any **xixj i<j** must be valid in the parent string too. Like "incl" is a substring of "includehelp" while "iel" 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 substring** 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 substring is: 10
Second test case:
Input string:
"abaaba"
Output:
Total count of palindromic sub-sequence is: 11

**Explanation:**

Test case 1: Input: "aaaa"

The valid palindromic sub-sequences are shown below:

Marked cells are character taken in subsequence:

So on...

**Total 10 palindromic substrings.**

Actually in this case since all the character is same each and every substring is palindrome here.

For the second test case,

Few substrings can be,
"a"
"b"
"a"
"aba"
So on...
Total 11 such palindromic sub sequences

This can be solved by using DP bottom up approach,

dp[n][n]wherenbe the stringlengthto 0 and a Boolean 2D arraypal[n][n]to store whether the substrings are palindrome or not.Base case is that each single character is a palindrome itself. And for

lengthof two, i.e, if adjacent characters are found to be equal then[i][i+1]=3,pal[i][i+1]=true, else if characters are different thendp[i][i+1]=2,pal[i][i+1]=falseTo 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 substrings are "a", "a", "aa".dp[0][n-1];So for higher lengths if

startingandendingindex is same then we recur for the remaining characters, since we have the sub-problem result stored so we computed that. In casestartandendindex character are different then we have addeddp[start+1][end]anddp[start][end-1]that's similar to recur for leavingstartingindex and recur for leavingendindex. 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: