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