String equality

Hi, today I will be presenting my thoughts on a recent codeforces problem. In this problem, we are given two strings $s$ and $t$ of length $n$. We want to make $s$ equal $t$ by performing any number of the following moves on $s$:

1. if we see 'ab' we can change it to 'ba',
2. if we see 'bc' we can change it to 'cb'.

We are asked to print YES if $s$ can be made equal to $t$, and NO otherwise. Note that $n\leq 10^5$, so we need $O(n\log{n})$ or better.

Firstly, we note that both moves leave the number of occurrences of each letter in $s$ and $t$ invariant. Thus, we count the number of occurrences of 'a', 'b', and 'c' in $s$ and $t$ and check they are equal.

Obs 1: Move $1$ moves 'b' to the left, and move $2$ moves 'b' to the right.

So moves essentially shift around the 'b' 's.

Obs 2: Let $\text{pos_s}_i$ be the position of the $i$th 'b' from the left of $s$, and let $\text{pos_t}_i$ be the position of the $i$th 'b' from the left of $t$. If $s$ is made equal to $t$, then $\text{pos_s}_i=\text{pos_t}_{i}$ for all $1\leq i\leq \text{cnt}_b$. 

Since $\text{pos_s}_i<\text{pos_s}_{i+1}$, the observation follows.

Once all 'b' 's are correctly positioned (if possible), i.e. $\text{pos_s}_{i}=\text{pos_t}_i$, then we cannot perform any more moves without moving a 'b' to the wrong position. Therefore, it only remains to check that the strings are equal, if so then we return YES, else we return NO.

This can be implemented in $O(n)$.