retagged by
895 views

1 Answer

Best answer
5 votes
5 votes
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.
edited by

Related questions

3 votes
3 votes
2 answers
3
iarnav asked Jun 3, 2018
5,029 views
Time complexity of Multistage Graph is O(n2) or O(V2) but then some people says it's O(E). So, from O(V2) to O(E) are they taking about dense/complete graphs in which num...