Let \(\lvert S\rvert\) denote the length of \(S\).
Note that a substitution never changes the string’s length.

There are various ways to solve this problem. We will introduce two of them.

Solution \(1\). step back and resume searching after performing an operation

One can find the position where the first operation is applied (or find that it will never be performed at all) by inspecting length-\(2\) substrings of \(S\) from the beginning one by one. Specifically, for each \(i=1,2,\ldots,\lvert S\rvert-1\) in order, check if the substring from the \(i\)-th through \((i+1)\)-th characters coincide with WA or not.
Now suppose that we have replaced the \(k\)-th through \((k+1)\)-th characters \((1\leq k\leq \lvert S\rvert-1)\) of the string from WA with AC. What will the next operation?
Since the \(k\)-th through \((k+1)\)-th characters have been chosen by the previous operation, the \(1\)-st through \((k-1)\)-th characters never contain WA as a substring. Therefore, the first position that WA can possibly appear as a substring is from the \((k-1)\)-th through \(k\)-th characters.
Thus, the next position to perform the operation can be spotted by inspecting the substring from the \(i\)-th through \((i+1)\)-th characters for each \(i=k-1,k,\ldots,\lvert S\rvert-1\) in order, and finding the first occurrence of WA. The entire procedure terminates when it reaches the last character after repeating this operation.

In order to analyze the computational complexity of this simulation, we need to notice the following fact:

• When performing operations against \(S\), the substitution of the substring from the \(i\)-th through \((i+1)\)-th characters occur at most once for each \(1\leq i\leq \lvert S\rvert-1\).

This is because performing the substitution of the \(i\)-th through \((i+1)\)-th characters makes the \((i+1)\)-th character C, which never changes anymore by any operations, and the \(i\)-th through \((i+1)\)-th characters never become WA.

Now let us consider the complexity. The number of substrings to be inspected is at least \(\lvert S\rvert-1\), but the execution of the replacement increases it by two. This is because, after inspecting the \(k\)-th through \((k+1)\)-th characters, we advance to the \((k+1)\)-th through \((k+2)\)-th characters if the operation is not performed, but we need to resume from the \((k-1)\)-th through \(k\)-th characters if the operation is performed. However, as mentioned above, the operations is performed at most \(\lvert S\rvert-1\) times, so there are at most \(O(\lvert S\rvert)\) length-two substrings to inspect. Therefore, the time complexity of this solution is \(O(\lvert S\rvert)\), which is fast enough.
Therefore, the problem has been solved.

Solution \(2\)

…will be translated later.

Sample code in C++ (Solution \(1\)):

#include <bits/stdc++.h>
using namespace std;

int main(void){
	string s;
	int n,cur=0;
	cin>>s;
	n=s.size();
	while(cur<(n-1)){
		if((s[cur]=='W')&&(s[cur+1]=='A')){
			s[cur]='A';
			s[cur+1]='C';
			if(cur>0)cur--;
		}
		else cur++;
	}
	cout<<s<<endl;
	return 0;
}

Sample code in C++ (Solution \(2\)):

#include <bits/stdc++.h>
using namespace std;

int main(void){
	string s;
	cin>>s;
	int n=s.size();
	for(int i=n-2;i>=0;i--){
		if((s[i]=='W')&&(s[i+1]=='A')){
			s[i]='A';
			s[i+1]='C';
		}
	}
	cout<<s<<endl;
	return 0;
}