Specialty String

Research found the official Codeforces Round 1084 editorial for 2200C. Its key hint is to think of the operation as deleting characters instead of replacing them with *, and its accepted-code idea is either repeated adjacent-pair deletion or a stack cancellation pass. The supplied statement matches that exactly.

The annoying-looking * condition is actually the whole trick. Suppose we look only at the characters that are not *. Their relative order never changes. A move chooses two equal non-* characters with only * between them, meaning they are adjacent in the current remaining string.

So the game is equivalent to this simpler process:

• Start with string $s$.
• In one move, delete adjacent equal characters $s_i=s_{i+1}$.
• Win iff the string can become empty.

That is the full reduction. No hidden magic. The stars are just deleted characters wearing a cheap disguise.

Now process the string from left to right using a stack:

• If the stack is nonempty and its top equals the current character $c$, pop the top.
• Otherwise, push $c$.

At the end, answer YES iff the stack is empty.

Why this works:

The operation is the rewrite rule

$$xx \to \varepsilon$$

for any lowercase letter $x$. The stack algorithm computes the reduced form after applying all possible adjacent equal cancellations.

We need to justify that this greedy reduction does not accidentally choose the wrong pair. Consider any place where choices could conflict. The only real overlap is something like $xxx$: deleting the first two or the last two both leaves exactly $x$. For longer runs, the same idea repeats. Different letters cannot conflict because only equal adjacent letters may be removed. Therefore the final reduced string is unique.

The stack maintains this invariant:

After reading the first $i$ characters, the stack equals the reduced form of the prefix $s_1s_2\dots s_i$.

When reading a new character $c$:

• If the reduced prefix ends in $c$, then that final $c$ and the new $c$ cancel, so popping is correct.
• Otherwise, no cancellation with $c$ is currently possible, so pushing is correct.

By induction, after all $n$ characters, the stack is the unique reduced form of the entire string. The original game is winnable exactly when this reduced form is empty.

Edge cases:

• If $n$ is odd, the stack cannot end empty, so the algorithm naturally prints NO.
• A single character cannot be deleted.
• Strings like aaaa reduce fully: aa cancels, then aa cancels.
• Strings like abba do not reduce fully: no adjacent equal pair appears at the start, so there is no legal first move.

Complexity is clean:

$$O(n)$$

per test case, with

$$O(n)$$

memory. Since $\sum n \le 5000$, this is miles under the limit.