Codechef Lunchtime 08 Question 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