# problem in understanding approach of CHRL2

Hi, im having problem in understanding the approach mentioned in the editorial of this problem - https://www.codechef.com/LTIME08/problems/CHRL2 . Please can someone share a better/easy approach ??

Thanks

1 Like

Lets Understand this question from bottom up manner. Here we need the word CHEF as sub-sequence. Since we maintain the count of every consecutive word to 0 i.e., C=CH=CHE=CHEF=0. Now to count of word CHEF we need to check whether βCHEβ word occur before the letter βFβ in sub-sequence or not. And for sub-sequence βCHEβ we need to check whether βCHβ occur prior to the letter βEβ or not. And for βCHβ we need to check only the letter βCβ occur prior to the letter βHβ or nor.

So According to this, whenever we encounter the letter βCβ just increment the Count of βCβ and move on. Now whenever we encounter the letter βHβ, we first check whether βCβ has been visited or counted or not. If It has been counted then we will increment the counter of βCHβ and decrements the count of βCβ because we have counted this letter in βCHβ. Same process repeats for rest of the word.

I hope you will get this simple explanation rather than scary DP which is mentioned in editorial. Here is the same code mentioned in First comment of editorial.

``````#include<iostream>
#include<cstdio>
#include<cstring>
char a[100005];
int main(){

scanf("%s",a);

int i,c,ch,che,chef;
c=ch=che=chef=0;

for(i=0;i<strlen(a);i++){
if(a[i]=='C'){
c++;
}
else if(a[i]=='H'){
if(c>0){c--; ch++;}
}
else if(a[i]=='E'){
if(ch>0){ch--; che++;}
}
else if(a[i]=='F'){
if(che>0){che--; chef++;}
}
}
printf("%d\n",chef);
return 0;
}``````

Thanks a lot!! It helped!!

1 Like
//