Problem Statement

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

Example 1:

Input:
S = 'bccb'
Output: 6
Explanation:
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

Problem Link

Count Different Palindromic Subsequences - LeetCode

Reference Video

https://www.youtube.com/watch?v=fvYlinirmFg&ab_channel=Pepcoding

Approach

Correction: In the above pic for Case2b) +1 is added too represent "cc"

Case 2c): m contains ≥ c's

Consider the string from i to j is "a...a...a... a" where there are at least two character 'a' close to leftmost and rightmost 'a' Eg: "aacaa" while i = 0 and j = 4: the dp[i + 1][j - 1] records the palindrome {"a", "c", "aa", "aca"}. the reason why dp[i + 1][j - 1] * 2 counted is that we count dp[i + 1][j - 1] one time as {"a", "c", "aa", "aca"}, and additional time as {"aaa", "aca", "aaaa", "aacaa"}. Now there is duplicate : {"aca"}, which is removed by deduce dp[next[i] + 1][pre[i] - 1]. So totally dp[i][j] record {"a", "c", "aa", "aca", "aaa", "aaaa", "aacaa"}

Code

int countPalindromicSubsequences(string S) {
        
       unordered_map <char,int> mp;
       int n = S.size();
        
       vector <int> next(n,-1),pre(n,-1);
        
       for(int i=0;i<n;i++)
       {
           if(mp.find(S[i])!=mp.end())
               pre[i] = mp[S[i]];
           
               mp[S[i]] = i;
       }
       mp.clear();
        
       for(int i=n-1;i>=0;i--)
       {
           if(mp.find(S[i])!=mp.end())
               next[i] = mp[S[i]];
           
               mp[S[i]] = i;
       }
        
        vector<vector<int >> dp(n,vector<int>(n));
        //Do not use int dp[n][n] if final answer has be answer%1000000007
       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] = 2;
               
               else
               {
                   if(S[i]!=S[j])
                       dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
                   else
                   {
                       if(next[i]>pre[j])
                           dp[i][j] = 2*dp[i+1][j-1] + 2;
                       
                       else if(next[i]==pre[j])
                           dp[i][j] = 2*dp[i+1][j-1] + 1;
                       
                       else
                           dp[i][j] = 2*dp[i+1][j-1] - dp[next[i]+1][pre[j]-1];
                   }
               }
               **dp[i][j] = dp[i][j] < 0 ? dp[i][j] + 1000000007 : dp[i][j] % 1000000007**;
           }
       }
        return dp[0][n-1];
    }