Who Watches the Watchpig?

A watchpig pair always looks like R ... L. The useful move is not to count all pairs globally; total pair count tells us basically nothing about whether each piggy is safe. We need the number of pairs containing one specific piggy.

Pair count for one piggy

Consider position $i$ in the final arrangement, using 1-based indexing.

• If piggy $i$ faces R, it can only be the left endpoint of a watchpig pair. Its pair count is the number of Ls strictly to its right.
• If piggy $i$ faces L, it can only be the right endpoint. Its pair count is the number of Rs strictly to its left.

Even before knowing any directions, this gives positional upper bounds:

• An L at position $i$ has at most $i-1$ possible partners.
• An R at position $i$ has at most $n-i$ possible partners.

These crude bounds are enough to solve the entire problem. Greedy problems occasionally decide to be nice.

Forced directions

For every $i\le k$, we have $i-1<k$. Thus a piggy among the first $k$ positions could never be safe while facing L. Every valid final arrangement must therefore begin with $k$ Rs.

Likewise, for every $i\ge n-k+1$, we have $n-i<k$. Such a piggy could never be safe while facing R. Every valid final arrangement must therefore end with $k$ Ls.

So every valid final string has the shape

$$\underbrace{RR\ldots R}_{k}\quad\text{anything}\quad\underbrace{LL\ldots L}_{k}.$$

When is it impossible?

If $2k>n$, the forced prefix and forced suffix overlap. Any position in the overlap would have to be both R and L, which is not a clever edge case; it is just impossible.

If $2k\le n$, the two regions are disjoint. Better yet, enforcing them is already sufficient:

• Any piggy facing L is outside the first $k$ positions. The first $k$ piggies are all R and all lie to its left, so it belongs to at least $k$ pairs.
• Any piggy facing R is outside the last $k$ positions. The last $k$ piggies are all L and all lie to its right, so it also belongs to at least $k$ pairs.

Therefore every middle direction works. We do not need to optimize it, simulate pairs, or summon a DP from the void.

Minimizing flips

The first $k$ positions are forced to become R, so every original L there must be flipped. The last $k$ positions are forced to become L, so every original R there must be flipped. These flips are unavoidable in every valid answer.

When $2k\le n$, perform exactly those flips and leave the middle unchanged. The sufficiency argument above proves that all piggies are then safe. Hence the lower bound is attained, and the minimum is

$$\#\{i\le k:s_i=L\}+\#\{i>n-k:s_i=R\}.$$

For example, in the last sample, the first four characters contain three directions that are not R, and the last four contain two directions that are not L, giving $3+2=5$ flips.

Correctness proof

Lemma 1. In every valid final arrangement, the first $k$ piggies face R and the last $k$ piggies face L.

Proof. A piggy facing L at position $i\le k$ has at most $i-1<k$ piggies to its left, so it cannot belong to $k$ watchpig pairs. Thus each of the first $k$ piggies must face R. Symmetrically, an R at position $i\ge n-k+1$ has at most $n-i<k$ piggies to its right, so each of the last $k$ piggies must face L. $\square$

Lemma 2. A valid arrangement exists exactly when $2k\le n$.

Proof. If $2k>n$, the two regions from Lemma 1 overlap, forcing at least one piggy to face both directions, so no valid arrangement exists.

Now suppose $2k\le n$. Set the first $k$ directions to R and the last $k$ to L, leaving the middle arbitrary. Every L has the first $k$ Rs to its left, and every R has the last $k$ Ls to its right. Thus every piggy belongs to at least $k$ watchpig pairs. $\square$

Lemma 3. When $2k\le n$, the algorithm returns the minimum number of flips.

Proof. By Lemma 1, every L in the first $k$ positions and every R in the last $k$ positions must be flipped, so the algorithm's count is a lower bound. Flipping exactly those piggies creates the arrangement used in Lemma 2, which is valid, without flipping any middle piggy. Therefore that lower bound is achievable and optimal. $\square$

Theorem. The algorithm outputs -1 exactly for impossible test cases; otherwise, it outputs the minimum number of flips needed to make every piggy safe.

Proof. The impossibility decision follows from Lemma 2, and optimality in every feasible case follows from Lemma 3. $\square$

Complexity

Each test case inspects only the first and last $k$ characters, taking $O(k)$ time and $O(1)$ extra space.