Count all Palindromic Subsequence in a given String in C++

In this tutorial, we will be discussing a program to find the number of all palindromic subsequences in a given string.

For this we will be provided with a string. Our task is to find the number of palindromic subsequences that can be made in that given string.

Example

#include<iostream> #include<cstring> using namespace std; //returning total palindromic sequence int count_palin(string str){    int N = str.length();    //creating a 2D array    int cps[N+1][N+1];    memset(cps, 0 ,sizeof(cps));    for (int i=0; i<N; i++)       cps[i][i] = 1;    for (int L=2; L<=N; L++){       for (int i=0; i<N; i++){          int k = L+i-1;          if (str[i] == str[k])             cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;          else             cps[i][k] = cps[i][k-1] + cps[i+1][k] - cps[i+1][k-1];       }    }    return cps[0][N-1]; } int main(){    string str = "abcb";    cout << "Total palindromic subsequence are : " << count_palin(str) << endl;    return 0; }

Output

Total palindromic subsequence are : 6