## Monday, November 14, 2016

### Count All Palindromic Subsequence in a given String - GeeksforGeeks

Count All Palindromic Subsequence in a given String - GeeksforGeeks
Find how many palindromic subsequence (need not necessarily be distinct) can be formed in a given string. Note that the empty string is not considered as a palindrome.

```Initial Values : i= 0, j= n-1;

CountPS(i,j)
// Every single character of a string is a palindrome
// subsequence
if i == j
return 1 // palindrome of length 1

// If first and last characters are same, then we
// consider it as palindrome subsequence and check
// for the rest subsequence (i+1, j), (i, j-1)
Else if (str[i] == str[j)]
return   countPS(i+1, j) + countPS(i, j-1) + 1;

else
// check for rest sub-sequence and  remove common
// palindromic subsequences as they are counted
// twice when we do countPS(i+1, j) + countPS(i,j-1)
return countPS(i+1, j) + countPS(i, j-1) - countPS(i+1, j-1)
```
If we draw recursion tree of above recursive solution, we can observe overlapping Subprolems. Since the problem has overlapping subproblems, we can solve it efficiently using Dynamic Programming.
Time Complexity : O(N2)