0

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?

Mat
  • 202,337
  • 40
  • 393
  • 406
Jera
  • 1
  • Unrelated to your problem (well, maybe a *little* related): Please don't go to online "judge" or "competition" sites to learn programming. Your code does some things that are bad or outright invalid. The only good I can say about your code is that it's nicely indented and that you at least have some comments. If you want to learn C++ the "proper" way, like reading [some good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) or take some classes. – Some programmer dude Jan 26 '20 at 17:49
  • Another comment, there is no reason to get the size of the strings before the actual strings. Simply check for `if(a.length() != b.length())` and return if it's true. – Rietty Jan 26 '20 at 17:50
  • Noted @Rietty . – Jera Jan 26 '20 at 18:00

0 Answers0