https://www.codechef.com/viewsolution/15093175
This is my code for Chef and String(CHRL2).I did manage to get an AC for |s|<=2000 but got a TLE for 100000.Any hints on how i can improve my code? Thanks.
Its a basic dp question. You are getting TLE due to nested loops.
The key of doing this question is in asking yourself “till index i, how many “CHEF” strings can i form?”
Remember, its a sub-sequence, so order is important. Basically, the essence of my approach was starting from end of string, and checking how many chef strings we can form.
https://www.codechef.com/viewsolution/13797966
Note that I used updating answer as - arr[2]=min(arr[3],arr[2]+1); .
This means, that number of CHEF’s formed (strictly w.r.t to letter E/assuming we have enough ‘C’ and ‘H’) is minimum of (‘F’ encountered, count of ‘E’+1). Similarly doing for H and C did the trick for me 