Count Different Palindromic Subsequences


@sunrita I am only using "last" to compute prev and next as defined in the article. Specifically, next[i][0] will be the next occurrence of 'a' in S[i:], next[i][1] will be the next occurrence of 'b' in S[i:], and so on. Since every character S[i] is only one of four letters 'a', 'b', 'c', 'd', we only need to have next[i][0], next[i][1], next[i][2], and next[i][3].

@bin14 I start with
ans = 1
to count the empty string palindrome, and I subtract it off. I guarantee distinct results because I have separated my count into counting forms (such as a_a, b_b etc. described) that represent disjoint sets.

@gladtbx because in the case when the first and the last characters are equal, we will simply get two extra palindromic subsequences: First one, is a subsequence of length 1 consists of only first/last character, and the second one, is the whole subsequence starting from the first character and ending with the last character.

For the else, why can't you do something like this:
if 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 m in range(4): # count each one within subwindows [i+1][j1]
dp[k][i][j] += dp[m][i+1][j1]
dp[k][i][j] %= mod
else:
dp[k][i][j] = max(dp[k][i+1][j],dp[k][i][j1])%mod

@awice, I have a similar solution with Approach 1. And I don't think line 18 is needed
if (j == i+1) dp[k][i][j] = 2; // "aa" : {"a", "aa"}
Correct me if I am wrong

@gladtbx, actually the 2 is 'x' and 'xx', why we can add these two is because for all the other palindrome has already added the 'x' at the beginning and the end, so there is no palindrome like 'x' and 'xx' remain.

Can anybody help me to understand the definition of dp[k][i][j] in the first method? I got the same idea and configured nearly the same solution but I didn't convince myself either. I still don't think the "dp[x][i][j] be the answer for the substring S[i...j] where S[i] == S[j] == 'a'+x" is right. For example, if the S is "abcd", then by definition, shouldn't dp[0][0][3], dp[1][0][3], dp[2][0][3], dp[3][0][3] all be equal to 0 because none of them reach the condition S[0] == S[3] == 'a' + x??? Any help are greatly appreciated cause I've been stuck here for all day...