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


Log in to reply
 

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