I was asked this question a while ago and I'm very stuck:
You have a sequence of
0
's and1
's, and you can perform one operation it: removing at least $K$ consecutive0
's or $K$ consecutive1
's from the sequence. After performing one of these operations, the ends of the sequence that are on the sides of the removed portion come together and close the gap created by the removal.Can you make operations such that the sequence becomes empty? If so, what is the least number of operations that you can make? I'm hazy on the restraints on the problem, but assume both $N$ and $K$ have at most two digits, and that $K$ is a lot smaller than $N$.
For example, say you have the sequence
1111000001
, and $K = 5$. The solution is to remove the middle line of0
's. You cannot remove any1
's on the first step, because the longest consecutive substring of1
's is only four long. Afterwards, however, the gap closes, and the sequence11111
is created, which can also be removed, creating the desired empty sequence. Only two operations are needed to make the sequence empty.
I believe that this is a DP problem, but I'm having trouble on what to represent as a state and how to construct a state from previous ones. Could anyone give me a hint?