Ghostfires

Maximum Length

Let $M$ be the largest of $r,g,b$, and let $S$ be the sum of the other two counts.

Even if the distance-$3$ rule did not exist, adjacency already says that $k$ copies of one color need at least $k-1$ non-that-color separators. So the most frequent color can contribute at most $S+1$ copies. Therefore every answer has length at most

$$L = S + \min(M,S+1).$$

This bound is tight. We keep all non-dominant colors, and if the dominant color has more than $S+1$ copies, we simply use only $S+1$ of it. Call the resulting target counts $c_0,c_1,c_2$, and let

$$n=c_0+c_1+c_2.$$

By construction,

$$\max(c_0,c_1,c_2) \le \left\lceil \frac n2 \right\rceil.$$

So the whole problem becomes: construct a valid string for any three target counts whose maximum is at most $\lceil n/2\rceil$. This is where the distance-$3$ rule stops looking like black magic.

Parity Trick

Both forbidden distances are odd:

$$1 \equiv 3 \equiv 1 \pmod 2.$$

So every forbidden pair connects an odd position to an even position. There are no constraints between two odd positions, and no constraints between two even positions. Nice. The beast has a zipper.

Let

$$o=\left\lceil \frac n2 \right\rceil, \qquad e=\left\lfloor \frac n2 \right\rfloor.$$

Think of building two arrays: one for odd slots and one for even slots, then interleaving them.

Easy Case

If some color has exactly $o$ copies, put that color in all odd slots. Put the other two colors, in any order, into the even slots.

Every forbidden pair is odd-even, and the odd color never appears on even positions, so no equal forbidden pair can happen. That is embarrassingly effective, which is the best kind of effective.

General Case

Otherwise, no color has $o$ copies. Sort the target counts:

$$a \ge b \ge c,$$

and call their colors $Y$, $X$, and $Z$, respectively. So $Y$ is the largest color, $X$ is the middle color, and $Z$ is the smallest color.

Fill the slots like this:

$$\text{odd slots} = X^{o-c}Z^c,$$ $$\text{even slots} = Y^aX^{e-a}.$$

Then interleave odd slot $1$, even slot $1$, odd slot $2$, even slot $2$, and so on.

The counts are exactly right:

$$\#Y=a,$$ $$\#Z=c,$$

and

$$\#X=(o-c)+(e-a)=n-a-c=b.$$

Now check validity. Color $Y$ appears only on even slots, and color $Z$ appears only on odd slots, so they cannot conflict with themselves because all forbidden edges are odd-even.

Only $X$ appears on both parities. Its odd occurrences are a prefix ending at odd-slot index $o-c$. Its even occurrences are a suffix starting at even-slot index $a+1$.

If there is no even $X$ suffix, there is nothing to prove. Otherwise $a<e$. Suppose $a+c\le o$. Then

$$b=n-a-c \ge e,$$

but also $b\le a<e$, contradiction. Hence

$$a+c\ge o+1.$$

So the first even $X$ is at least two slot-indices after the last odd $X$:

$$(a+1)-(o-c)=a+c-o+1\ge 2.$$

An odd slot $i$ is real position $2i-1$, and an even slot $j$ is real position $2j$. If $j-i\ge 2$, their real distance is

$$2j-(2i-1)=2(j-i)+1\ge 5.$$

So equal $X$ copies are never adjacent and never distance $3$ apart. Valid.

Complexity

The construction writes the answer once, so each test case costs

$$O(|s|)$$

time and memory. Over the whole input this is

$$O\left(\sum |s|\right),$$

which is easily fine because the total available ghostfires are bounded by $10^6$.