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