Paint the balls: what patterns can be painted?
Every pattern with a run of length $\ell$ is feasible. Indeed, consider first that the last run has length at least $\ell$. We go over the string from left to right, and for each $i$, we paint balls $i,i+1,\ldots,i+\ell-1$ with the required color for position $i$. After going over all possible indices (i.e., all but the last $\ell-1$), we have painted the pattern.

Now suppose that there is such a run in the middle, say $r,\ldots,s$. We run the algorithm above up to position $r-1$, and the we run a similar algorithm going from left to right, until ball $r$ is painted. We have painted the pattern.

As for the optimal number of moves, one natural algorithm to consider is the algorithm described above, with a simple optimization: when attempting to paint the $i$th ball, if it is already of the correct color, then don't bother. I conjecture that this algorithm, or some simple variant of it, is indeed optimal.