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.
Note that I used updating answer as -
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