# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* iceknight1093

*wasd2401*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

Prefix sums or binary search

# PROBLEM:

You’re given strings A and B of the same length, containing the characters `a`

, `b`

, `c`

.

In one move, you can choose any subsequence of A that’s `abc`

and make it `cba`

.

Can A be turned into B?

# EXPLANATION:

Let’s make a couple of observations about the process.

- The
`b`

’s never move from their positions. - The count of each character doesn’t change.

So, if the positions of `b`

’s in A and B don’t match, or the frequencies of their characters don’t match, the answer is immediately `No`

.

Otherwise, note that if A_i \neq B_i at some index, the only possibility is A_i = a and B_i = c, or vice-versa.

Let’s call these (a, c)- and (c,a)-indices respectively.

Let S_1 denote the sorted list of (a,c)-indices, and S_2 denote the sorted list of (c,a)-indices.

Observe that S_1 and S_2 must have the same size, because of the initial conditions that were checked.

Let this common size be k.

Then, the answer is `Yes`

*if and only if*:

- S_1[i] \lt S_2[i] for each 1 \leq i \leq k; and
- There exists a
`b`

between S_1[i] and S_2[i] for each 1 \leq i \leq k.

## Proof

Sufficiency should be obvious: if both conditions hold, it’s possible to swap the values at indices S_1[i] and S_2[i] for each i, which will ‘fix’ both those indices. Repeat for every i and A will equal B.

Now, we prove necessity.

First, suppose S_1[i] \gt S_2[i] for some i.

Consider the *smallest* i for which this happens.

Look at the prefix of A and B of length S_2[i] here. Observe that in this prefix, A will contain exactly one `c`

more than B.

However, our operation can only move `c`

’s left; meaning the number of `c`

’s in this prefix can only increase - so A will always have strictly more `c`

’s in this prefix than B. This means they can never be made equal!

Finally, suppose S_1[i] \lt S_2[i] for every i.

Look at S_1[k] and S_2[k].

- If there’s a
`b`

between them, great, swap them and move on to index k-1. - If there’s no
`b`

between them, it’s impossible to swap S_1[k] with*any*element of S_2.

In fact, you can see that if at all S_1[k] can be swapped, it must be with some index that’s greater than S_2[k] (so that a`b`

can exist), but then we know S_1[k] \gt S_2[k] has no solution.

So, if it’s possible to make A = B, there must be a`b`

between S_1[k] and S_2[k]. Then, move on to the previous indices and apply the same logic.

Checking whether S_1[i] \lt S_2[i] for every i is trivial after building S_1 and S_2.

Checking whether there’s a `b`

between each pair of corresponding indices isn’t hard either: for example, you can use binary search on a sorted list of the `b`

’s, or even prefix sums to count the number of `b`

’s in some range.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Tester's code (C++)

```
/*
* * * *** * *****
* * * * * * * *
* * * *** ***** *
* * * * * * * * *
* * * * * * **
*
* *
*****
* *
***** * *
_* *_
| * * * * | ***
|_* _ *_| * *
* * *
***** * **
* * ***
{===* *===}
* IS * ***
* IT * * *
* RATED?* *
* * * **
* * ***
* *
***** * *
* *
* *
* *
***
*/
// 2 Years Tribute to Competitive Programming
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()
const ll N = 2e5 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;
ll modinverse(ll a) {
ll m = mod, y = 0, x = 1;
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += mod;
return x;
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
ll product = 1;
a %= md;
while (b) {
if (b & 1) product = (product * a) % md;
a = (a * a) % md;
b /= 2;
}
return product % md;
}
void panipuri() {
ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
string s,t;
bool ch = true;
cin >> n>>s>>t;
vl a,b;
set<ll> st;
forl(i,0,n){
if(s[i]=='b'){
if(t[i]!='b'){
yesno(0);
return;
}
st.insert(i);
}
else if(t[i]=='b'){
yesno(0);
return;
}
else{
if(s[i]=='a') c++;
if(t[i]=='a') c--;
if(s[i]!=t[i]){
if(s[i]=='a') a.pub(i);
else b.pub(i);
}
}
}
if(c){
yesno(0);
return;
}
forl(i,0,a.size()){
auto it=st.lower_bound(a[i]);
auto it1=st.lower_bound(b[i]);
if(it==it1 || a[i]>b[i]){
yesno(0);
return;
}
}
yesno(1);
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int laddu = 1;
cin >> laddu;
forl(i, 1, laddu + 1) {
// cout << "Case #" << i << ": ";
panipuri();
cout << '\n';
}
}
```

## Editorialist's code (C++)

```
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string a, b; cin >> a >> b;
string ans = "Yes";
vector<array<int, 2>> ac, ca;
int bct = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == b[i]) {
bct += a[i] == 'b';
continue;
}
if (a[i] == 'b' or b[i] == 'b') {
ans = "No";
break;
}
if (a[i] == 'a') ac.push_back({i, bct});
else ca.push_back({i, bct});
}
if (ac.size() != ca.size()) ans = "No";
else {
int k = ac.size();
for (int i = 0; i < k; ++i) {
if (ac[i][0] > ca[i][0] or ac[i][1] == ca[i][1]) ans = "No";
}
}
cout << ans << '\n';
}
}
```