Let’s “shift” \(i\)-th character “to the left’” \(i\) times (where shifting goes in order A \(\to\) C \(\to\) B \(\to\) A). Now the operation transforms to another: we can choose any substring among AAA, BBB, CCC, and replace it with any other from them.

Note that we can transform string AAAX (where Xis any letter) to string XAAA: AAAX \(\to\) XXXX \(\to\) XAAA.

This means that basically we can “cut out” any \(3\) consecutive equal characters, and reinsert any string among AAA, BBB, CCC at any place in the string.

Let’s now call strings AAA, BBB, CCC good.

Now, I want to define the following invariant \(f(S)\) for the string \(S\), which doesn’t change during operations:

Let’s cut out substrings while we can (concatenating \(2\) remaining parts after each cutting out). Let’s call the remaining string (which contains no good substring) \(f(S)\).

It’s not clear that \(f(S)\) is well-defined: maybe if we make these deletions in different orders, we will get different strings. Let’s prove that it’s well-defined by induction.

Suppose that for all strings of size \(<|S|\), \(f\) is well-defined. If it has at most one good substring, clearly \(f(S)\) is well-defined, as there is only one (or zero) cutting out we can do right now.

Suppose that there are \(2\) different good substrings of \(S\), such that deleting them leads to different \(f(S)\). If these substrings don’t intersect, we get a contradiction, because when we delete the first of them, we can delete the second one, and \(f\) from the remaining string would be the same as if we deleted the second of them and then the first. So they have to intersect, but then they form a consecutive segment of equal letters, and deleting these substrings leads literally to the same string. So, \(f\) is well-defined.

I claim that we can transform \(S\) into \(T\) iff \(f(S) = f(T)\).

Firstly, if \(f(S) = f(T)\), it’s obvious that we can transform, as we can reinsert deleted good strings wherever we want.

Now we only have to show that \(f(S)\) doesn’t change when we do the operation. But it’s easy: we know that we can delete good substrings in any order, so we can delete the good substring we were replacing as well, meaning that \(f(S)\) doesn’t change.

So the algorithm is to calculate \(f(S)\) and \(f(T)\), and to check if they are the same. This can be done with stack in \(O(N)\), by adding characters one by one (with the transformation above), and deleting last \(3\) characters from it if they all turn out to be the same.