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