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!
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.
Hi, I am not sure I understand why that is the case, please help me here.
If
S[l] == S[r]thenI am doing:
1 + sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1)becauseThe 1 means the palin. subsequence "S[L]S[R]" (just 2 letters)
The
sol(l + 1, r)will cover palin. subseq fromS[l + 1, ... , r]andThe
sol(l, r - 1)will cover palin. subseq fromS[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!
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.
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 forS[l + 1, ... , r -1] = YThen since you counted twice:
YS[l]YS[r]which is also palindromicSo 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?
Yes.