Codechef CHRL2

dynamic-programming
lunch-time
lunchtime

#1

Codechef Lunchtime 08 Question CHRL2
http://www.codechef.com/problems/CHRL2

Editorial suggests a DP solution in O(n^2)

I was thinking of a different solution.
Obviously , I got a WA.
But I can’t figure out the mistake can anyone help ?

Suppose we store all the occurrences of C,H,E,F seperately.

Then we match each C to the first H which comes after it and then with first E that comes after H and first F that comes after E.
And proceed accordingly.

for eg. in CHHHEEEFFCC
vc -> 0, 9, 10
vh -> 1,2,3
ve -> 4,5,6
vf -> 7,8

now vc[0] = 0;
we can match it with 1(i.e H), 4, and 7
Now vc[1] = 9
There is no i such that vh > 9
Therefore program ends.

Can anyone point out the mistake ?

~Thanks