We can solve this problem in O(N^2) complexity using dynamic programming aproach with the help of 2 dimension table of
order (N * N)
where table[i][j] = count of number of pallendromic subesequence ( or subset ) lies in the interval [ i ...... j ].
Solvable in order of O(N^2)
This problem involves overlapping subproblems , when you make a tree for the above problem.
Extra expanation how to solve it :
Lets say we have a bit strng of length N ( 0 based indexing )
// recursive code to count number of subsequence( subset ) which are pallendrome.
_______________________________________________________________________________________________
function call will be : count( 0 , N - 1 , x ) // 0 is starting index , N - 1 is last position , x = binary string
int count( int i , int j , string x ) {
if(i > j) return 0; // i <= j ( Valid )
if(i == j) return 1; // single character is pallendrome
if( x[i] == x[j] ) // it means ith character is equals to jth character, combined both character will add one pallendrome
return count(i + 1 , j ) + count( i , j - 1 ) + 1 // two possiblites
else
return count(i + 1 , j ) + count(i , j - 1 ) - count( i + 1 , j - 1 )
// we are substracting count(i+1,j-1) becase some pallendrome which are counted in count(i+1,j) are also counted in
count(i , j - 1) so we have to remove those which count twice.
}
__________________________________________________________________________________________________
If you make a tree for any string for the above code you will see their are overlaping subproblems involved for any state [ i...j]
it may be called many times , so why we solve same state again and again.
Introduce a table of O(N^2) which will store the count of interval [ i.....j ] = means number of pallendrome present in the interval.
int table[N][N] // initiliase it with -1.
_______________________________________________________________________________________________
function call will be : count( 0 , N - 1 , x )
int count( int i , int j , string x ) {
if(i > j) return 0;
if(i == j) return 1;
if(table[i][j] != -1) return table[i][j] // means this interval is already solved somewhere else.
int result = 0;
if( x[i] == x[j] )
result = count(i + 1 , j ) + count( i , j - 1 ) + 1
else
result = count(i + 1 , j ) + count(i , j - 1 ) - count( i + 1 , j - 1 )
return table[i][j] = result // it will return the result to parent node as well as store the result in the table.
}
The above method is know as recursion + memoization ( also know as a type of recursive dynamic solution ( Bottom up ) )
__________________________________________________________________________________________________
Complexity of the above code will be O(N^2 ) because each state is solved only once. we can also write iterative solution using for loop in the same manner. But both are almost similar and have same complexity.
If you are not saving the state, then some state were calculated too many time , which make the complexity to exponential.
And the above code counts total number of subset which are pallendrome.
It's not for total number of distinct pallendromic subsequence.