My friend was asked this question in an interview:

We have a vector of integers consisting only of

`0`

s and`1`

s. 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 theminimumnumber of`delete`

s 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 `b`

s, 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++