aakarshmadhavan's blog

Count number of palindromic subsequences Top down
By aakarshmadhavan, history, 6 years ago, In English

Hello, The problem is just

Count the number of palindromic subsequences in a string (they can be duplicates),
Input : str = "aab"
Output : 4
Explanation :- palindromic subsequence are :"a", "a", "b", "aa"

Please help me come up with recursive solution.

public int sol(String s, int l, int r){
        if(r < l) return 0;
        if(l == r) return 1;
        
        int ans = 0;
        if(s.charAt(l) == s.charAt(r)){
            ans = 1 + sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1);
        } else {
            ans = sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1);
        }
        
        return ans;
    }

For test case s = "aaaa" this has failed (it is outputting 10 when the answer is actually 15)

Where am I going wrong? Thanks!

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

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

When s.charAt(l) == s.charAt(r) , do ans = 1 + sol(s, l + 1, r) + sol(s, l, r - 1); , because all subsequences in [l + 1 , r — 1] can be extended by the s[l] and s[r] characters.

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

    Hi, I am not sure I understand why that is the case, please help me here.

    If S[l] == S[r] then

    I am doing: 1 + sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1) because

    The 1 means the palin. subsequence "S[L]S[R]" (just 2 letters)

    The sol(l + 1, r) will cover palin. subseq from S[l + 1, ... , r] and

    The sol(l, r - 1) will cover palin. subseq from S[l, ... , r - 1]

    But both of these will cover palin. subseq from S[l + 1, ... , r - 1]

    So why shouldn't I subtract sol(s, l + 1, r - 1) once?

    Thanks!

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

      You should subtract once. But say s[l] = x , and Y is some palindromic subsequence in [l+1,r-1] , you dont count subsequences of the form xYx , so add solve(l+1,r-1) too.

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

        Hey!

        Ok I am starting to understand it, please tell me if this is correct: By subsequence below I mean palindromic subsequence

        Case S[l] == S[r]: - You have 1 subsequence = "S[l]S[r]" - You will add subsequences from S[l, ... , r — 1] --> Call this A - you will add subsequences from S[l + 1, ... , r] --> Call this B Now is the tricky part: Both A and B contain subsequences from S[l + 1, ... , r — 1], so you are counting it twice, but say the subsequence for S[l + 1, ... , r -1] = Y

        Then since you counted twice:

        • 1 count for just Y
        • 1 count for S[l]YS[r] which is also palindromic

        So that's why I don't do - sol(l + 1, r - 1)

        Final sum is:

        1 + sol(l, r - 1) + sol(l + 1, r)

        Is this accurate?

        → Reply