Hints: https://atcoder.jp/contests/arc166/editorial/7374

[1] The case with only A and B

First, let’s discuss the case where all characters are A or B. Here, the only operation to consider is Operation (3).

By focusing only on A, this operation can be seen as moving one A one position to the right, and the following can be proved:

Suppose \(X\) and \(Y\) are strings consisting of A and B.

Let \(i_1 < i_2 < \cdots < i_x\) be the \(i\)’s such that the \(i\)-th character of \(X\) is A. Let \(j_1 < j_2 < \cdots < j_y\) be the \(i\)’s such that the \(i\)-th character of \(Y\) is A.

The necessary and sufficient condition for \(X\) to be transformable into \(Y\) by Operation (3) is that \(x=y\) and \(i_k\leq j_k\) for every \(k\).

For the necessity, it is enough to show it in the case of one operation, which is simple. The sufficiency can be seen by considering moving the \(k\)-th A in \(X\) to the appropriate position in descending order of \(k\).

[2] Solution to the original problem

First, it is impossible to create a new character C by the operations. Therefore, the following must hold:

• If the \(i\)-th character of \(Y\) is C, then the \(i\)-th character of \(X\) must also be C.

If this necessary condition does not hold, the answer is No.

When this condition holds, the problem can be solved by dividing \(Y\) at the positions of C and checking each substring.

By dividing it in this way, the problem can be reduced to the case where \(Y\) consists of A and B.

Suppose \(Y\) consists only of A and B. Consider how we should perform Operations (1) and (2) for C in \(X\).

First, by counting the number of A and B in the string, you can determine how many C in \(X\) should be converted to A and B. Furthermore, it will be easiest to satisfy the condition in [1] if we convert Cs that are as far to the left as possible to A, and convert Cs that are as far to the right as possible to B. By checking the condition in [1] after such conversion, you can solve this problem.