Problem Statement

Given a string str of length N, you have to find number of palindromic subsequence (need not necessarily be distinct) which could be formed from the string str. Note: You have to return the answer module 10^9+7;

Example 1:

Input:
Str = "abcd"
Output:
4
Explanation:
palindromic subsequence are : "a" ,"b", "c" ,"d"

Example 2:

Input:
Str = "aab"
Output:
4
Explanation:
palindromic subsequence are :"a", "a", "b", "aa"

Problem Link

https://www.geeksforgeeks.org/count-palindromic-subsequence-given-string/

Approach

Code

long long int countPS(string str)
    {
       int n = str.size();
       vector<vector<int >> dp(n,vector<int>(n));
        for( int gap=0;gap<n;gap++)
        {
            for(int i=0,j=gap;j<n;i++,j++)
            {
                if(gap==0)
                    dp[i][j] = 1;
                
                else if(gap==1)
                dp[i][j] = str[i]==str[j] ? 3 : 2;
                
                else 
                if(str[i]==str[j])
                    dp[i][j] = 1 + dp[i][j-1] + dp[i+1][j];
                
                else 
                    dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
            
                **dp[i][j] = dp[i][j] < 0 ? dp[i][j] + 1000000007 : dp[i][j] % 1000000007;**
            }
        }
        return dp[0][n-1];
    }