Approach #1 Dynamic Programming [Accepted]
Intuition and Algorithm
Let dp[x][i][j]
be the answer for the substring S[i...j]
where
S[i] == S[j] == 'a'+x
. Note that since we only have 4 characters a, b, c, d
, thus 0 <= x < 4
. The DP formula goes as follows:

If
S[i] != 'a'+x
, thendp[x][i][j] = dp[x][i+1][j]
, note that
here we leave the first characterS[i]
in the window out due to
our definition ofdp[x][i][j]
. 
If
S[j] != 'a'+x
, thendp[x][i][j] = dp[x][i][j1]
, leaving the
last characterS[j]
out. 
If
S[i] == S[j] == 'a'+x
, thendp[x][i][j] = 2 + dp[0][i+1][j1] + dp[1][i+1][j1] + dp[2][i+1][j1] + dp[3][i+1][j1]
. When the first and last characters are the same, we
need to count all the distinct palindromes (for each ofa,b,c,d
) within
the subwindowS[i+1][j1]
plus the2
palindromes contributed by
the first and last characters.
Let n
be the length of the input string S
, The final answer would
be dp[0][0][n1] + dp[1][0][n1] + dp[2][0][n1] + dp[3][0][n1]
mod 1000000007
.
C++
class Solution {
public:
int countPalindromicSubsequences(string S) {
int n = S.size();
int mod = 1000000007;
auto dp_ptr = new vector<vector<vector<int>>>(4, vector<vector<int>>(n, vector<int>(n)));
auto& dp = *dp_ptr;
for (int i = n1; i >= 0; i) {
for (int j = i; j < n; ++j) {
for (int k = 0; k < 4; ++k) {
char c = 'a' + k;
if (j == i) {
if (S[i] == c) dp[k][i][j] = 1;
else dp[k][i][j] = 0;
} else { // j > i
if (S[i] != c) dp[k][i][j] = dp[k][i+1][j];
else if (S[j] != c) dp[k][i][j] = dp[k][i][j1];
else { // S[i] == S[j] == c
if (j == i+1) dp[k][i][j] = 2; // "aa" : {"a", "aa"}
else { // length is > 2
dp[k][i][j] = 2;
for (int m = 0; m < 4; ++m) { // count each one within subwindows [i+1][j1]
dp[k][i][j] += dp[m][i+1][j1];
dp[k][i][j] %= mod;
}
}
}
}
}
}
}
int ans = 0;
for (int k = 0; k < 4; ++k) {
ans += dp[k][0][n1];
ans %= mod;
}
return ans;
}
};
Example Walkthrough
Indeed this is a hard problem to solve and thoroughly understanding
its solution is also challenging. Maybe the best way to understand the
above approach is to walkthrough some simple examples to help build up
intuitions.
Complexity Analysis

Time complexity : $$O(n^2)$$ where $$n$$ is the length of the input
string $$S$$. It takes quadratic time to fill up the DP table. 
Space complexity : $$O(n^2)$$ where $$n$$ is the length of the input
string $$S$$. The DP table takes quadratic space.
Note that we ignore the constant factor $$4$$ in the above analysis.
Conclusion
As we look back, this problem reveals a key attribute which indicates
that dynamic programming might be a good fit: overlapping subproblems
as we recall the DP formula. By practicing more
problems, we can build up this kind of intuition.
Credit: the above solution is inspired by
this post
written by @lastico. His solution is space optimized. However, I found
that my approach is relatively easy to understand for people who found
this problem hard to approach.