Maximum Color Segment

The number of color segments is

$$1 + \#\{i \mid s_i \ne s_{i+1}\}.$$

So the real game is not about characters. It is about the gaps between characters.

Let

$$b_i = [s_i \ne s_{i+1}] \qquad 1 \le i < n.$$

We want to maximize the number of $1$s among these $b_i$'s, then add $1$ at the end.

What One Operation Really Does

Suppose we flip the substring $[l, l+k-1]$.

For a gap strictly inside the substring, both adjacent characters are flipped, so whether they are equal/different does not change. For a gap strictly outside, nothing changes.

Only the two boundary gaps can change:

• gap $l-1$, if it exists;
• gap $l+k-1$, if it exists.

To make the boundary cases clean, add two dummy gaps:

• gap $0$ before the string,
• gap $n$ after the string.

They contribute nothing to the score. Then every operation toggles exactly two gaps:

$$l-1 \quad \text{and} \quad l+k-1.$$

These two gap indices differ by exactly $k$.

So the problem becomes:

We have vertices $0,1,\dots,n$. Vertices $1,\dots,n-1$ have values $b_i \in \{0,1\}$ and score $1$ if their final value is $1$. Vertices $0,n$ have score $0$. One operation toggles two vertices whose indices differ by $k$. Use at most $m$ operations to maximize score.

That is the whole trick. The substring thing was wearing a fake mustache.

Splitting By Modulo $k$

An operation connects gap $x$ with gap $x+k$. Therefore indices never change modulo $k$.

So each residue class forms an independent chain:

$$r,\ r+k,\ r+2k,\dots$$

Inside one chain, an operation toggles two adjacent vertices of that chain.

Different chains do not interact except that they share the global operation budget $m$.

Now we need, for each chain, compute:

$$best_c[t] = \text{maximum score obtainable in this chain using exactly } t \text{ operations}.$$

Then we knapsack-combine all chains using at most $m$ operations.

DP For One Chain

Take one chain of vertices $v_0, v_1, \dots, v_{q-1}$.

There is an edge between consecutive vertices. Choosing an edge means performing the corresponding length-$k$ flip, toggling both endpoints.

For a vertex $v_i$, its final parity is affected by:

• the edge from $v_{i-1}$ to $v_i$,
• the edge from $v_i$ to $v_{i+1}$.

So while scanning left to right, we only need to know whether the current vertex has already been toggled by the previous edge.

Let $dp[used][p]$ mean: after processing up to the current position's incoming state, we have used used operations, and the current vertex has incoming toggle parity $p$ from the previous edge.

At vertex $v_i$, choose whether to take the outgoing edge to $v_{i+1}$:

$$x \in \{0,1\}.$$

Then the final value of this vertex is

$$initial(v_i) \oplus p \oplus x.$$

If $v_i$ is a real gap, it contributes that final value. If it is dummy gap $0$ or $n$, it contributes $0$ no matter what.

Then the next vertex has incoming parity $x$.

For the last vertex, there is no outgoing edge, so $x=0$ only.

This computes the best score for this chain for every operation count.

Important detail: the global problem allows at most $m$ operations, not exactly $m$. So after combining chains, take the maximum over all operation counts $0 \le t \le m$.

Why This Is Correct

Every original operation corresponds to toggling two gap vertices distance $k$ apart, and every such pair corresponds to exactly one valid length-$k$ substring flip. So the transformed graph problem is equivalent.

The graph splits into residue classes modulo $k$, because every edge preserves the index modulo $k$. Hence choices in different chains are independent, except for the total operation count.

For one chain, each operation is exactly choosing one edge. The final value of a vertex depends only on the chosen edge to its left and the chosen edge to its right. When scanning left to right, the left edge is already known as parity $p$, and the right edge is the current binary decision $x$. Therefore the chain DP considers every possible subset of edges exactly once and scores it correctly.

Finally, knapsack over chains tries every distribution of the operation budget among independent chains. That gives the global optimum.

No magic, just gap algebra. Annoyingly elegant, as usual.

Complexity

Each chain DP costs proportional to

$$O(\text{chain length} \cdot m).$$

The total length of all chains is $n+1$, so all chain DPs together cost $O(nm)$.

Combining chains also costs $O(nm)$ total if we only keep reachable operation counts up to $m$.

Memory usage is $O(m)$ per DP array, plus small chain storage.