Problem Link :Here
Now This question states find longest palindromic subsequence of S containing the character C.
So Normal Solution without any constraint of Char c is to iterate over String in forward and reverse direction with i-starting from 0 j- starting from length-1
and do normal thing to include or skip
Now in this question i also used boolean flag to check whether character c has been appeared or not till now
public static int solvePalindroimic(int i,int j, boolean isTrue){
if(i>j){// 0,0,false //1 5 false
return 0;
}
if(i==j){
if(isTrue==true ||(isTrue==false &&word[i]==x)){
return 1;
}
else{
return 0;
}
}
boolean res = word[i]==x?true:isTrue;//0 , 0 ,false res =false//1 ,1 res =false
int ans = 0;
if(word[i]==word[j]){
ans= solvePalindroimic(i+1,j-1,res);//solve(1,5,false)
if(ans==0){
return 0;
}
else{
return ans+2;
}
}
ans =Math.max(solvePalindroimic(i,j-1,res),solvePalindroimic(i+1,j,word[j]==x?true:isTrue));
if(ans==0){
return 0;
}
else{
return ans;
}
}
if it detect character at any index it return ans or 0 and if it detects return value to be zero than it means no character C is found
this recurrence is working could anyone tell memoized solution please how to formulate it