There are 2 strings A and B with lowercase alphabets. I can perform any number of operations on the string A. An operation would consist of replacing all instances of a character in string A with any other character.
For example, if string A = “abaabc” and we perform an operation of replacing character b with character d, it becomes adaadc. Further if we replace character a with b it becomes bdbbdc.
Is it possible to convert string A to string B?
My approach:
I basically found out the frequencies of A and B and then found out all possible subset sums of A's frequency set. If any frequency of B is not in that subsetsum set, then I print NO.
la and lb
represent lengths of A and B, and t
is for number of testcases.
#include<bits/stdc++.h>
using namespace std;
vector<int> getFreq(string s){
vector<int> arr(26, 0);
for(int i=0; i<s.size(); i++)
arr[s[i]-'a']++;
vector<int> freq;
for(int i=0; i<26; i++){
if(arr[i])
freq.push_back(arr[i]);
}
sort(freq.begin(), freq.end());
return freq;
}
void subsetSum(vector<int> arr, vector<int> &res)
{
int n = arr.size();
int sum = 0;
for (int i=0; i<n; i++)
sum += arr[i];
// dp[i][j] would be true if arr[0..i-1] has
// a subset with sum equal to j.
bool dp[n+1][sum+1];
memset(dp, 0, sizeof(dp));
// There is always a subset with 0 sum
for (int i=0; i<=n; i++)
dp[i][0] = true;
// Fill dp[][] in bottom up manner
for (int i=1; i<=n; i++)
{
dp[i][arr[i-1]] = true;
for (int j=1; j<=sum; j++)
{
// Sums that were achievable
// without current array element
if (dp[i-1][j] == true)
{
dp[i][j] = true;
dp[i][j + arr[i-1]] = true;
}
}
}
// Print last row elements
for (int j=0; j<=sum; j++)
if (dp[n][j]==true)
res.push_back(j);
}
int main() {
int t;
cin >> t;
while(t--){
int la, lb;
cin >> la >> lb;
string a, b;
cin >> a;
cin >> b;
if(la != lb){
cout<<"NO"<<endl;
continue;
}
vector<int> afreq = getFreq(a);
vector<int> bfreq = getFreq(b);
vector<int> res;
subsetSum(afreq, res);
bool flag = false;
for(int i=0; i<bfreq.size(); i++){
if(find(res.begin(), res.end(), bfreq[i]) == res.end()){
cout<<"NO"<<endl;
flag = true;
break;
}
}
if(flag)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
return 0;
}
Is my approach correct?