PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Sibasish Ghosh
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Easy
PREREQUISITES:
Ordered-Map/Frequency Array , Observation
PROBLEM:
Problem-statement
Given two strings S_1 and S_2 , both of same length.
Each index i of S_1 has a type t_i , and swapping characters between two indices of same type is allowed in S_1.
Print “Yes” if you can convert S_1 to S_2 after any number of valid swaps, otherwise print “No”.
EXPLANATION:
Lets define F1[x] = set of characters in string S1 having type x.
and F2[x] = set of characters in string S2 having type x.
Now notice that , as we can swap any two positions having same type, the order of the character doesn’t matter at all.
If F1[x] equals F2[x] , then that means we have same set of characters in both the strings under type ‘x’. We can simply rearrange the characters in S2 to match the position of characters in S1.
So for each type, we have to only check if the set of characters is same in both strings.
See setter solution for implementation.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifdef Zoro
freopen("/home/pritish/Competitive/in", "r", stdin);
freopen("/home/pritish/Competitive/out", "w", stdout);
#endif
int t;
cin>>t;
long long sumn=0;
while(t--)
{
int n;
cin>>n;
sumn+=n;
string s1,s2;
cin>>s1>>s2;
int a[n];
map<int,string>m1,m2;
for (int i = 0; i < n; ++i)
{
cin>>a[i];
m1[a[i]].push_back(s1[i]);
m2[a[i]].push_back(s2[i]);
}
int ok=1;
for(auto [t,x]:m1)
{
auto y=m2[t];
sort(x.begin(), x.end());
sort(y.begin(), y.end());
if(x!=y)
{ok=0;}
}
if(ok)cout<<"Yes\n";
else cout<<"No\n";
}
cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1,sum=0;
cin>>t;
assert(1 <= t && t <= 100000);
while(t--)
{
ll n,i,j;
cin>>n;
assert(1 <= n && n <= 100000);
sum+=n;
assert(sum <= 100000);
string s1,s2;
cin>>s1>>s2;
ll val[n+10],cnt[n+10][26],f=1;
memset(cnt,0,sizeof(cnt));
for(i=0;i<n;i++)
{
cin>>val[i];
assert(1 <= val[i] && val[i] <= n);
assert('a' <= s1[i] && s1[i] <= 'z');
assert('a' <= s2[i] && s2[i] <= 'z');
cnt[val[i]][s1[i]-'a']++;
cnt[val[i]][s2[i]-'a']--;
}
for(i=1;i<=n;i++)
{
for(j=0;j<26;j++)
{
if(cnt[i][j] != 0)
{
f=0;
break;
}
}
if(!f) break;
}
if(f)
cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}