Count Different Palindromic Subsequences


  • 1

    Click here to see the full article post


  • 0
    S

    Why is the list 'last' defined as last = [None] * 4? What is the significance of 4?


  • 0

    @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].


  • 0
    B

    I have so many questions wish someone could kindly help me out... Why ans is initialized to 1 in function dp(i, j)? How the solution guarantees distinct results? Why the final result dp(0, N-1) needs to minus 1? Thanks in advance!


  • 0

    @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.


  • 0
    J

    Considering there is a "-1" in the final result, the return value of function dp should lie in the interval [1, MOD]. So we'd better change "if (ans>=MOD) ans-=MOD;" to "if (ans>MOD) ans-=MOD;". Anyway, it's a precise and efficient approach.


  • 0
    G

    In solution 1, why do you do +2 for each pair?


  • 0
    S

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


  • 0

    May I know why we need mod 1e9 + 7 ?


  • 0
    C

    can someone explain how approach #2 solve "aaa"?


  • 0
    L

    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][j-1]
    dp[k][i][j] += dp[m][i+1][j-1]
    dp[k][i][j] %= mod
    else:
    dp[k][i][j] = max(dp[k][i+1][j],dp[k][i][j-1])%mod


  • 0

    @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


  • 0
    J

    @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.


  • 0
    F

    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...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.