aakarshmadhavan's blog

Count different palindromic subsequences
By aakarshmadhavan, history, 6 years ago, In English 
Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.
A subsequence of a string S is obtained by deleting 0 or more characters from S.
A sequence is palindromic if it is equal to the sequence reversed.
Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

**EXAMPLE - 1:**
Input: 
S = 'bccb'
Output: 6
Explanation: 
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

I am trying to get a recursive algorithm/solution, I will memoize it later on.

So my algorithm right now is:

public int countPalindromicSubsequences(String S) {
        return (int) (helper(S, 0, S.length() - 1)%1000000007);
    }
    
    public int helper(String s, int l, int r){
        if(r - l < 0) return 0;
        if(r - l == 1) return 2;
        if(r - l == 0) return 1;
        int sol = 0;
        if(s.charAt(l) == s.charAt(r)){
            sol = helper(s, l + 1, r - 1);
        } 
        sol += helper(s, l + 1, r);
        sol += helper(s, l, r - 1);  
        return sol;
    }

This doesn't seem to work right now, can someone help me out and point the mistakes/improvements? Thanks

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Consider: sol += helper(s, l + 1, r); sol += helper(s, l, r — 1);

Both will eventually have the option to go to helper(s,l + 1,r — 1), so you are counting helper(s,l + 1,r — 1) twice, subtract that.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In string with length of N, there are at most N(maybe 2N? not really sure..) palindrome subsequences. The proof is same with "why Manacher's algorithm has O(N) time complexity". To explain more, we keep max(i + dp[i]) during the algorithm, and that is upper bound of distinct number of subsequence palindromes.

*however that is not same thing you want to calculate. I guess you should eliminate subsequences that is not different.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The proof is actually very simple: If you add a letter to the end of S, at most one new palindrome can appear. All new palindromes which could appear have their right end at the new character, and all but the largest of them are already contained in S by being reflections of themselves around the largest palindrome.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In addition O (n log n) is available with suffix array and LCP. There might be another solution i couldnt find

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      These observations don't really hold when it comes to subsequences (not substrings). I've actually proposed this problem on CSA some time ago, and you can check out the editorial here.

      → Reply