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?
 
    