Count different palindromic subsequences

Правка en1, от aakarshmadhavan, 2018-07-14 10:09:32
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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский aakarshmadhavan 2018-07-14 10:09:32 1411 Initial revision (published)