DP - Removing contiguous subsequences from a sequence optimally

Question

I was asked this question a while ago and I'm very stuck:

You have a sequence of 0's and 1's, and you can perform one operation it: removing at least $K$ consecutive 0's or $K$ consecutive 1'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 of 0's. You cannot remove any 1's on the first step, because the longest consecutive substring of 1's is only four long. Afterwards, however, the gap closes, and the sequence 11111 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?

Answer 1

1. First collect the consecutive alphabets together. Say the input string is "1110000110100" then I mean form the array $A=\{(3,1),(4,0),(2,1),(1,0),(1,1),(2,0)\}$ where an element ( called chunk ) of $A$ $(a,b)$ means there are $a$ consecutive $b \in \{0,1\}$. Now the problem has been reduced to removal of chunks and we will concern ourselves with $A$ rather than the original string.
2. Now make a DP table $D$ where $D[i][j][k]$ means least number of steps used to removed all chunks till $A[i]$ such that last chunk removed was of $k \in \{0,1\}$ and the size of the last chunk removed was $j$. If it is not possible assign it $\infty$ ( take care of the boundary cases and initial condition for table $D$ ).
3. Now say you are at chunk $i$ and it is a chunk made of 0's and it's size is $t$. Now you have to fill the table $D[i][][]$ given that you have already filled the tables $D[1][][],D[2][][]......D[i-1][][]$. You have two options (a) If $t \ge K$ remove this chunk first and now you are left with subproblem with $A[1]...A[i-1]$; (b) or if its possible to remove the chunks of 1's before , and then if the chunk of 0's get's size greater than equal to $K$, you can remove it ( rwe will take minimum of all cases while filling the DP table ). As you asked for only hint I leave it upto you for coming up with the recurrence relation.

As you said $N$ and $K$ are small, I think this method would suffice.