Colorful Stamp
Contest: Codeforces Round 784 (Div. 4)
Difficulty rating: 1100
Tags: implementation

A row of $$$n$$$ cells is given, all initially white. Using a stamp, you can stamp any two neighboring cells such that one becomes red and the other becomes blue. A stamp can be rotated, i.e. it can be used in both ways: as $$$\color{blue}{\texttt{B}}\color{red}{\texttt{R}}$$$ and as $$$\color{red}{\texttt{R}}\color{blue}{\texttt{B}}$$$.

During use, the stamp must completely fit on the given $$$n$$$ cells (it cannot be partially outside the cells). The stamp can be applied multiple times to the same cell. Each usage of the stamp recolors both cells that are under the stamp.

For example, one possible sequence of stamps to make the picture $$$\color{blue}{\texttt{B}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\color{blue}{\texttt{B}}\texttt{W}$$$ could be $$$\texttt{WWWWW} \to \texttt{WW}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\texttt{W} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\texttt{W} \to \color{blue}{\texttt{B}}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}\texttt{W}$$$. Here $$$\texttt{W}$$$, $$$\color{red}{\texttt{R}}$$$, and $$$\color{blue}{\texttt{B}}$$$ represent a white, red, or blue cell, respectively, and the cells that the stamp is used on are marked with an underline.

Given a final picture, is it possible to make it using the stamp zero or more times?

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the picture.

The second line of each test case contains a string $$$s$$$ — the picture you need to make. It is guaranteed that the length of $$$s$$$ is $$$n$$$ and that $$$s$$$ only consists of the characters $$$\texttt{W}$$$, $$$\texttt{R}$$$, and $$$\texttt{B}$$$, representing a white, red, or blue cell, respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
Output $$$t$$$ lines, each of which contains the answer to the corresponding test case. As an answer, output "YES" if it possible to make the picture using the stamp zero or more times, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first test case is explained in the statement.

For the second, third, and fourth test cases, it is not possible to stamp a single cell, so the answer is "NO".

For the fifth test case, you can use the stamp as follows: $$$\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{blue}{\texttt{B}}$$$.

For the sixth test case, you can use the stamp as follows: $$$\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}$$$.

For the seventh test case, you don't need to use the stamp at all.

Example input:
12
5
BRBBW
1
B
2
WB
2
RW
3
BRB
3
RBB
7
WWWWWWW
9
RBWBWRRBW
10
BRBRBRBRRB
12
BBBRWWRRRWBR
10
BRBRBRBRBW
5
RBWBW

Example output:
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO

Editorial:
First note that parts of the picture separated by $$$\texttt{W}$$$ are independent. That is, any stamps used on one part doesn't have any impact on the other, since a character $$$\texttt{W}$$$ means no stamp has been placed on that cell. So let's split the string by $$$\texttt{W}$$$s (for example, with split() method in Python), and consider the resulting strings containing only $$$\texttt{R}$$$ and $$$\texttt{B}$$$. Call one of these parts $$$p$$$.
In the final stamp we place on $$$p$$$, we must have placed $$$\texttt{RB}$$$, so it should have both the characters $$$\texttt{R}$$$ and $$$\texttt{B}$$$. Therefore, if the string has only $$$\texttt{R}$$$ or only $$$\texttt{B}$$$, the answer is NO.
Otherwise, the answer is YES. Let's show it. As we have just shown, we must have $$$\texttt{R}$$$ next to $$$\texttt{B}$$$ for the string to be possible. Consider the way to make $$$\texttt{RBRRBBBB}$$$. The final stamp can be $$$\texttt{RBR}\underline{\texttt{RB}}\texttt{BBB}$$$. For the rest of the cells, we can make them one by one as below. $$$$$$\texttt{WWWWWWWW} \to \underline{\texttt{RB}}\texttt{WWWWWW} \to \texttt{R}\underline{\texttt{BR}}\texttt{WWWWW} \to \texttt{RB}\underline{\texttt{RB}}\texttt{WWWW}\text{,}$$$$$$ so now we have made the prefix of the string before the final stamp. Similarly: $$$$$$\texttt{RBRBWWWW} \to \texttt{RBRBWW}\underline{\texttt{RB}} \to \texttt{RBRBW}\underline{\texttt{RB}}\texttt{B} \to \texttt{RBRB}\underline{\texttt{RB}}\texttt{BB}\text{.}$$$$$$ Now we have made the prefix and the suffix by stamping "one character" at a time (actually, we stamp two characters, but then cover it up with another stamp).
Finally, we can put the final stamp to make the whole string. $$$$$$\texttt{RBRBRBBB} \to \texttt{RBR}\underline{\texttt{RB}}\texttt{BBB}\text{.}$$$$$$ This method easily generalizes to any string. We can find the final stamp and then make the prefix and suffix one by one. The solution runs in $$$\mathcal{O}(n)$$$.