• In this problem, we need to print the count of palindromic subsequences in string str
• The naive approach to get the count would be to explore all the possible subsequences and after that to check whether that subsequence is a palindrome or not.
• This way, the time complexity becomes O((2^n) * n). As the possible number of subsequences will be 2^n (n being the length of the input string) and then to check each subsequence it would take O(n) time.
• But we wish to do this in O(n^2). HOW?
• Well, before moving to that, we need to develop some relation between the possible subsequences. Let's take an example to understand that. Consider a string 'abcd'.
• To find all the subsequences of 'abcd', we divide the string in three parts, c1, c2 and mid. In this case, c1 is 'a', c2 is 'd' and mid is 'bc'.
• With the help of possible subsequences of 'bc' which is mid, we can derive all other subsequences also as shown above. By adding 'a' in front of all subsequences of 'bc', by adding 'd' at the end of all possible subsequences of 'bc' and then by adding 'a' in front and 'd' at the end of all ...... YOU KNOW RIGHT?
• So we can generalize the results as above.
• All the possible subsequences of a string containing c1 (first character), mid (middle part) and c2 (last character), can be written in the form of all the possible subsequences of the mid.
• All the possible subsequences of a string containing c1 (first character), and mid (middle part), can be written in the form of all the possible subsequences of the mid. As 'c1' can be either added or not.
• All the possible subsequences of a string containing mid (middle part) and c2 (last character), can be written in the form of all the possible subsequences of the mid. As 'c2' can be either added or not to the middle part.
• If we can get all the subsequences then we can also count the ones which are palindromes.
• As you can see above, count of palindromic subsequences (cps) of the given string is also equal to cps of the all the possible subsequences of mid plus cps of all the possible subsequences of mid when c2 is added at last plus cps of all the possible subsequences of mid when c1 is added in front plus of all the possible subsequences of mid when c1 is added in front and c2 is added at last.
• This can also be summarized further, by knowing if 'c1' and 'c2' are equal or not.
• If 'c1' and 'c2' are equal, it means that all the possible subsequences generated out of 'bc' which are palindromes will remain unaffected by the addition of similar characters at the beginning and at the end. However there will be addition of one more subsequence i.e. 'c1c2' in the blank. That's why we have replaced C4 with C1 +1 while summarizing the formulas in case c1 and c2 are equal.
• But if 'c1' and 'c2' are not equal, it means that all the possible subsequences generated out of 'bc' which are palindromes will be affected by the addition of different characters at the beginning and at the end. That's why we have replaced C4 with 0 while summarizing the formulas in case c1 and c2 are not equal.
• Further we have just reframed the formula by grouping, addition and subtraction.
• Now using dynamic programming and gap strategy we will fill the dp matrix using the optimal summarized formulas after checking whether c1 and c2 are equal or not.

For more clarity of this part, watch part of the video.

Let's take an example and understand this in a better way.

• Consider the string 'abccbc' and build a 2D matrix corresponding to this.
• And at any dp[i][j], the cell will store the count of palindromic subsequences of substring of 'abccbc' starting from i and ending on j.
• Like, dp[1][4] will correspond to the substring which starts from 1st character i.e. b and ends with 4th character i.e. b corresponding to the substring 'bccb'.
• Lower part of the matrix will be invalid as the subsequences are supposed to follow the sequence of the string.
• And to fill this matrix, we will use the gap strategy and therefore we will fill it diagonally.
• Talking of diagonal 0 (first), the cells correspond to a single character string and a single character string is a palindrome. So in this diagonal, we can directly fill 1.
• Now moving to diagonal 1, the cells correspond to two character strings. And from now onwards, we will fill the cells of the matrix using the formulas which we have already summarized.
• The only task left is to fill the dp matrix using these formulas after checking if the first and last character of the particular substring are equal or not.
• Like at dp[0][1], c1 i.e. 'a' and c2 i.e. 'b' are not equal. So the formula that we will use is cps(c1 mid) + cps(mid c2) - cps(mid). And as there is no mid, so the components left are cps(c1) + cps (c2).
  And as here c1 is 'a' and c2 is 'b'. So we need to look at cells which correspond to substring 'a' and 'b' i.e. dp[0][0] and dp[1][1] respectively. To get the final result we need to add the values present at these two dps, dp[0][0] + dp[1][1] which is 1+1=2. Finally, store 2 corresponding to substring 'ab' i.e. at dp[0][1].
• Now talking of dp[2][3], c1 i.e. 'c' and c2 i.e. 'c' are equal. So the formula that we will use is cps(c1 mid) + cps(mid c2) + 1. And as there is no mid, so the components left are cps(c1) + cps (c2) +1.
  And as here c1 is 'c' and c2 is 'c'. So we need to look at cells which correspond to substring 'c' and 'c' i.e. dp[3][3] and dp[4][4] respectively. To get the final result we need to add the values present at these two dps and then add 1 to it, dp[0][0] + dp[1][1] + 1 which is 1+1+1=3. Finally, store 3 corresponding to substring 'cc' i.e. at dp[2][3]. Similarly you can fill the rest of the matrix.
• Now moving to the next diagonal, let's try to fill dp[0][3] which corresponds to substring 'abc'. Here c1 i.e. 'a' and c2 i.e. 'c' are not equal. So the formula that we will use is cps(c1 mid) + cps(mid c2) - cps(mid). And as here c1mid is 'ab', c2mid is 'bc' and mid is 'c'. So we need to look at cells which correspond to substring 'ab', 'bc' and 'c' i.e. dp[0][1], dp[1][2] and dp[1][1] respectively. To get the final result we need to substitute the values present at these dps into the formula, dp[0][1] + dp[1][2] - dp[1][1] which is 2+2-1=3. Finally, store 3 corresponding to substring 'abc' i.e. at dp[0][2].
• Now let's try to fill dp[3][5] which corresponds to substring 'cbc'. Here c1 i.e. 'c' and c2 i.e. 'c' are equal. So the formula that we will use is cps(c1 mid) + cps(mid c2) + 1.
  And as here c1mid is 'cb' and c2mid is 'bc'. So we need to look at cells which correspond to substring 'cb' and 'bc' i.e. dp[3][4] and dp[4][5] respectively. To get the final result we need to substitute the values present at these dps into the formula, dp[3][4] + dp[4][5] +1 which is 2+2+1=5. Finally, store 5 corresponding to substring 'cbc' i.e. at dp[3][5]. Similarly fill the complete diagonal and rest of the matrix.
• Try to fill the rest of the matrix on your own and after that you can cross check your result from the above matrix.
• And then the value present at dp[0][dp[0].length()-1] will be the final answer. In this case '16' is present at dp[0][5] which means that there are 16 subsequences which are palindromes.

For more clarity of this part, watch part of the video.

Let's try to code this!

• To start with, define a 2D matrix of dimensions str.length() * str.length().
• hen to use the gap strategy, we will apply a nested 'for' loop to travel the dp matrix diagonally.
• After entering this nested 'for' loop, first of all check whether gap (g) is zero or not. And if it is zero then simply put '1' at dp[i][j].
• Then check if the gap is one or not. If yes, then check whether the first and second characters are equal or not. And if they are not equal then put 2 and if not then put 3 at dp[i][j].
• And if gap is neither zero nor one, then come to the else part. Here check if character at ith index of string (first character of substring) is equal to jth character of string (last character of substring).
  And if yes, then put dp[i+1][j] + dp[i][j - 1] + 1 at dp[i][j]. Otherwise put dp[i+1][j] + dp[i][j - 1] - dp[i + 1][j - 1] at dp[i][j].
• At last return dp[0][dp[0].length()].

For more clarity of the code, watch part of the video.