[[string]] [[thinking]]
link
\(AA\) \(BB\) \(ABAB\) \(BCBC\) are given, ask whether string \(a\) can become string \(b\).
Inserting and deleting at any position are approved.
Sol
Firstly, the parity of the occurrences of \(A\), \(B\) and \(C\) are same in \(a\) and \(b\).
Then, we can transform the string \(AB\) to the string \(BA\) via the following sequence of moves:
Start with \(AB\), then insert \(BB\) at the back of the string to get \(ABBB\), then insert the string \(ABAB\) in the second to last position to get \(ABBABABB\).
Removing the two occurrences of \(BB\) we get the string \(AABA\) and then removing \(AA\) we get to \(BA\).
Similarly, we can transform the string \(BC\) to the string \(CB\).
Therefor, \(B\) is movable and their positions are of no great importance.
\(A\) and \(C\) is immovable, so I only need to compare the string consist of \(A\) and \(C\).
Code
#include<bits/stdc++.h>
using namespace std;
int t,la,lb,pa,pb,pc;
string a,b;
int main(){
scanf("%d",&t);
for(;t--;){
cin>>a>>b;
la=a.length();
lb=b.length();
pa=pb=pc=0;
for(int i=0;i<la;i++){
if(a[i]=='A')pa^=1;
if(a[i]=='B')pb^=1;
if(a[i]=='C')pc^=1;
}
for(int i=0;i<lb;i++){
if(b[i]=='A')pa^=1;
if(b[i]=='B')pb^=1;
if(b[i]=='C')pc^=1;
}
if(pa||pb||pc){
printf("NO\n");
continue;
}
for(int i=0;i<la;i++)if(a[i]=='B')a.erase(i,1),la--,i--;
for(int i=0;i<lb;i++)if(b[i]=='B')b.erase(i,1),lb--,i--;
for(int i=0;i<la-1;i++)if(a[i]==a[i+1])a.erase(i,2),i=max(-1,i-2),la-=2;
for(int i=0;i<lb-1;i++)if(b[i]==b[i+1])b.erase(i,2),i=max(-1,i-2),lb-=2;
if(a==b)printf("YES\n");
else printf("NO\n");
}
}