Minimum number of `delete`s to make vector empty

  algorithm, c++

My friend was asked this question in an interview:

We have a vector of integers consisting only of 0s and 1s. A delete consists of selecting consecutive equal numbers and removing them. The remaining parts are then attached to each other. For e.g., if the vector is [0,1,1,0] then after removing [1,1] we get [0,0]. We need one delete to remove an element from the vector, if no consecutive elements are found.
We need to write a function that returns the minimum number of deletes to make the vector empty.

For e.g., in case of [0,1,1,0], we need 2 deletes whereas in case of [1,0,1,0], we need 3 deletes:
[1,0,1,0] -> [0,1,0] -> [0,0] -> [].

Pseudo code below:

I am unsure how to solve this question. I feel that we can use a greedy approach:

a. Remove all consecutive equal elements and increment the delete counter for each;
b. Remove elements of the form <a, b, c> where a==c and a!=b, because of we had multiple consecutive bs, it would have been deleted in step (a) above. Increment the delete counter once as we delete one b.
c. Repeat steps (a) and (b) as long as we can.
d. Increment delete counter once for each of the remaining elements in the vector.

But I am not sure if this would work. Could someone please confirm if this is the right approach? If not, how do we solve this?

Thanks.

Source: Windows Questions C++

LEAVE A COMMENT