Intuition and Algorithm\nNot necessarily distinct palindromic\nAssume that we are interested counting, not necessarily distinct palindromic subsequences. This is dynamic programming (DP) problem.\n\nDP(L, R), is the number of palindromic subsequences in S[L .... R]. Its formulated as following.\n* 0 , if L>R\n* 1 , if L=R\n* DP(L + 1, R) + DP(L, R-1) - DP(L+1, R-1) , if S[L] != S[R]\n* DP(L + 1, R) + DP(L, R-1) + 1 , if S[L] = S[R]\n\n**Why the third one?**\nCheck the below image, if S[L] != S[R] then DP(L,R) is represented by blue (line) + green (line) - red (line) ,the last one is because of repeated elements between blue and green lines.\n\n![image](https://assets.leetcode.com/users/hamlet_fiis/image_1554893505.png)\n\n**Why the fourth one?**\n\nFirst assume that S[L]!= S[R], the formula is: *DP(L + 1, R) + DP(L, R-1) - DP(L+1, R-1)*\nConsider S = a.....b...a...b.....a\nNow check when S[L]= S[R], we have to add all palindromes that contains *(L+1,R-1)* because they are bordered by a character + 1 (only the border).\nThe formula will be: *DP(L, R) = (DP(L + 1, R) + DP(L, R-1) - DP(L+1, R-1)) + (DP(L+1, R-1)+1 )*, solving that , we have.\nDP(L, R) = DP(L + 1, R) + DP(L, R-1) + 1\n \nDistinct palindromic\nDP(L, R, alpha), is the number of distinct palindromic subsequences in S[L .... R] bordered by alpha. . Its formulated as following.\n\nDP(L, R, alpha), is the number of palindromic subsequences in S[L .... R]. Its formulated as following.\n* 0 , if L>R or (L=R and S[L]!=alpha)\n* 1 , if L=R and S[L]=alpha\n* DP(L + 1, R, alpha) + DP(L, R-1,alpha) - DP(L+1, R-1,alpha) , if S[L] != S[R]\n* 2+ SUM(DP(L+1,R-1, Betha) ) where Betha is all the alphabet , if S[L] = S[R] and S[L]=alpha\n\n**Why the third one?**\nSimilar that , not necessarily distinct palindromic.\n**Why the fourth one?**\nIts easy to verify.\nS[L......R] = [a.......b......a]\n 2+ SUM(DP(L+1,R-1, Betha) ), number 2 is because of getting ( **a** and **aa**)\nthe sum is the result of getting palindromes with border **a**.\n\n**C++**\n

\n\n\tint memo[1001][1001][4];\n\tclass Solution {\n\tpublic:\n\t\tstring S;\n\t\tint MOD = 1000000007;\n\t\n\t\tint dp(int start,int end,int alpha){\n\t\t\t//base case\n\t\t\tif(start>end)return 0;\n\t\t\tif(start==end){\n\t\t\t\tif(S[start] == (alpha+\'a\') )return 1;\n\t\t\t\treturn 0;\n\t\t\t}\n\t\t\t\n\t\t\tif(memo[start][end][alpha]!=-1)return memo[start][end][alpha];\n\t\t\t\n\t\t\tint dev=0;\n\t\t\tif(S[start]==S[end] && S[start]==(alpha+\'a\')){\n\t\t\t\tdev=2;\n\t\t\t\tfor(int i=0;i<4;i++)\n\t\t\t\t\tdev=(dev + dp(start+1,end-1,i) )%MOD;\n\t\t\t}else{\n\t\t\t\tdev= (dev + dp(start,end-1,alpha))%MOD;\n\t\t\t\tdev= (dev + dp(start+1,end,alpha))%MOD;\n\t\t\t\tdev= (dev - dp(start+1,end-1,alpha))%MOD;\n\t\t\t\tif(dev<0)dev+=MOD;\n\t\t\t}\n\t\t\t\n\t\t\tmemo[start][end][alpha]=dev;\n\t\t\treturn dev;\n\t\t}\n\t\t\n\t\tint countPalindromicSubsequences(string _S) {\n\t\t\tS=_S;\n\t\t\tmemset(memo,-1,sizeof(memo));\n\t\t\tint ans=0;\n\t\t\t\n\t\t\tfor(int i=0;i<4;i++)\n\t\t\t\tans= (ans + dp(0, S.size()-1, i))%MOD;\n\t\t\t\n\t\t\treturn ans;        \n\t\t}\n\t};\n

\n\n\n

Complexity Analysis

\n

\n
Time Complexity: $O(N^2)$ , where $N$ is length of S and alphabet is 4 (a,b,c,d).
\n
\n
Space Complexity: $O(N)$ .\n
\n
\n

Count Different Palindromic Subsequences

Problem Description

Problem Description

Answer Panel