Evolution of Weasels
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: greedy, implementation, strings

A wild basilisk just appeared at your doorstep. You are not entirely sure what a basilisk is and you wonder whether it evolved from your favorite animal, the weasel.

How can you find out whether basilisks evolved from weasels? Certainly, a good first step is to sequence both of their DNAs. Then you can try to check whether there is a sequence of possible mutations from the DNA of the weasel to the DNA of the basilisk.

Your friend Ron is a talented alchemist and has studied DNA sequences in many of his experiments. He has found out that DNA strings consist of the letters A, B and C and that single mutations can only remove or add substrings at any position in the string (a substring is a contiguous sequence of characters). The substrings that can be removed or added by a mutation are AA, BB, CC, ABAB or BCBC. During a sequence of mutations a DNA string may even become empty.

Ron has agreed to sequence the DNA of the weasel and the basilisk for you, but finding out whether there is a sequence of possible mutations that leads from one to the other is too difficult for him, so you have to do it on your own.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains a string $$$u$$$ ($$$1\le |u|\le 200$$$) — the DNA of the weasel.

The second line of each test case contains a string $$$v$$$ ($$$1\le |v|\le 200$$$) — the DNA of the basilisk.

The values $$$|u|$$$, $$$|v|$$$ denote the lengths of the strings $$$u$$$ and $$$v$$$. It is guaranteed that both strings $$$u$$$ and $$$v$$$ consist of the letters A, B and C.

Output format:
For each test case, print YES if there is a sequence of mutations to get from $$$u$$$ to $$$v$$$ and NO otherwise.

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

Example input:
8
A
B
B
C
C
A
AA
BB
BB
CC
CC
AA
ABAB
BCBC
ABC
CBA

Example output:
NO
NO
NO
YES
YES
YES
YES
NO

Editorial:
To solve the problem we need the following observations.
• Every mutation is reversible. Hence, instead of trying to find a sequence of mutations of the string $$$u$$$ to get to the string $$$v$$$, we can try to find a sequence of mutations of the string $$$u$$$ and a sequence of mutations of the string $$$v$$$ such that both of them are the same after the mutations.
• In all possible mutations, we never change the parity of the occurrence of a character. Thus, if the parity of the occurrences of $$$\texttt{A}$$$, $$$\texttt{B}$$$ and $$$\texttt{C}$$$ is not the same in $$$u$$$ and $$$v$$$, there does not exist a sequence of mutations to get from $$$u$$$ to $$$v$$$. For the rest of the solution we assume that the parities are the same in both strings.
We can transform the string $$$\texttt{AB}$$$ to the string $$$\texttt{BA}$$$ via the following sequence of moves: start with $$$\texttt{A}\texttt{B}$$$, then insert $$$\texttt{B}\texttt{B}$$$ at the back of the string to get $$$\texttt{ABBB}$$$, then insert the string $$$\texttt{ABAB}$$$ in the second to last position to get $$$\texttt{ABBABABB}$$$. Removing the two occurences of $$$\texttt{B}\texttt{B}$$$ we get the string $$$\texttt{A}\texttt{A}\texttt{B}\texttt{A}$$$ and then removing $$$\texttt{A}\texttt{A}$$$ we get to $$$\texttt{B}\texttt{A}$$$. A similar trick can be done to transform the string $$$\texttt{BC}$$$ to the string $$$\texttt{CB}$$$. While this series of steps might seem magical, viewing the problem as a group theoretic problem (see a later section) gives us this observation almost for free.
The observation above tells us that we can move the letter $$$\texttt{B}$$$ to any position we want and can essentially ignore it; let $$$u'$$$ and $$$v'$$$ be the strings we obtain from $$$u$$$ and $$$v$$$ when removing all occurrences of $$$\texttt{B}$$$. When ignoring the letter $$$\texttt{B}$$$, the strings $$$\texttt{ABAB}$$$ and $$$\texttt{BCBC}$$$ are the same as the strings $$$\texttt{AA}$$$ and $$$\texttt{CC}$$$, thus we now have strings consisting of the letters $$$\texttt{A}$$$ and $$$\texttt{C}$$$ and we can add and remove substrings of the form $$$\texttt{AA}$$$ and $$$\texttt{CC}$$$. This is a much easier problem. We can iteratively remove occurences of $$$\texttt{AA}$$$ or $$$\texttt{CC}$$$ from $$$u'$$$ and $$$v'$$$ until no removal is possible anymore. If the strings are the same after the removal, a sequence of mutations is possible, otherwise it is not.
Optimizing the runtime. If we remove occurrences of $$$\texttt{AA}$$$ and $$$\texttt{CC}$$$ iteratively the runtime of our algorithm is quadratic (in the length of the strings), which is fast enough to pass. There exists a linear time algorithm: Keep a stack of the substring you visited but could not remove (at the beginning, this is empty). Then iterate through your string. If the letter you currently look at is the same as the last letter in your stack, delete the last letter in your stack. If not add the letter to your stack.
Viewing the problem as a group theoretic problem
This is a different perspective on the problem and might require some knowledge about groups and their presentations to understand. In the language of groups, the problem statement can be reformulated as follows: Do the words $$$u$$$ and $$$v$$$ represent the same element in the group $$$G=\{\texttt{A},\texttt{B}, \texttt{C}\mid\texttt{A}^2 = \texttt{B}^2=\texttt{C}^2 = \texttt{ABAB} = \texttt{BCBC} = 1\}$$$? The words $$$u$$$ and $$$v$$$ represent the same element if and only if $$$w = uv^{-1}$$$ represents the identity in $$$G$$$. Furthermore $$$\texttt{A}$$$ and $$$\texttt{B}$$$ commute: $$$\texttt{A}^2 = 1$$$ implies that $$$\texttt{A} = \texttt{A}^{-1}$$$ and the same holds for $$$\texttt{B}$$$ and $$$\texttt{C}$$$. Thus, $$$1 = \texttt{A}\texttt{B}\texttt{A}\texttt{B} = \texttt{A}\texttt{B}\texttt{A}^{-1}\texttt{B}^{-1}$$$, which directly implies $$$\texttt{AB} = \texttt{B}\texttt{A}$$$. Analogously, we get that $$$\texttt{BC} = \texttt{CB}$$$.
Now the only thing left to check is:
• Does the letter $$$\texttt{B}$$$ occur evenly many times in $$$w$$$?
• After deleting all occurences of $$$\texttt{B}$$$ from $$$w$$$, can we get from $$$w$$$ to the empty word by deleting $$$\texttt{AA}$$$ or $$$\texttt{CC}$$$?
If the answer to one of those questions is no, then $$$w$$$ does not represent the identity. If both answers are yes, $$$w$$$ does represent the identity.
Some background about the problem. The problem of telling whether two words represent the same element in a group is called the word problem, and is a widely studied problem in Mathematics. While it is proven to be unsolvable for some groups, the group $$$G$$$ we are dealing with in this problem is a Coxeter group, where the word problem is always solvable using Tits' algorithm.