name reduction problem of CodeChef

 This is a fairly simple but a little tricky problem, try thinking about the problem and not the details mentioned in the problem statement.

This is the Official Problem Statement:-

In an attempt to reduce the growing population, Archer was asked to come up with a plan. Archer being as intelligent as he is, came up with the following plan:

If $N$ children, with names $C_{1}, C_{2}, ... , C_{N}$, are born to parents with names $A$ and $B$, and you consider $C$ to be the concatenation of all the names of the children, i.e. $C = C_{1} + C_{2} + ... + C_{N}$ (where $+$ is concatenation operator), then $C$ should be a substring of one of the permutations of $A + B$.

You are given the task to verify whether the names parents propose to give their children are in fact permissible by Archer's plan or not.

Input

The first line contains an integer $T$, the number of test cases. $T$ test cases follow. Each test case stats with a line containing two space separated strings $A$ and $B$, denoting the names of the parents. The next line contains a single integer $N$ denoting the number of children $A$ and $B$ are planning to have. Following this are $N$ lines, the $i^{th}$ line containing $C_{i}$, the proposed name for the $i^{th}$ child.

Output

For each test case output a single line containing $YES$ if the names are permissible by Archer's plan, otherwise print $NO$.

Constraints

• $ 1 \leq T \leq 100 $
• $ 1 \leq N \leq 1000 $
• The lengths of all the strings including $A$, $B$, and all $C_{i}$ will be in the range $[1, 40000]$, both inclusive. All these strings will contain only lowercase English letters.
• The combined lengths of all names of children will not exceed the combined length of the names of their parents.

Sample 1:

Input

Output

3
tom marvoloriddle
2
lord
voldemort
cheap up
1
heapcup
bruce wayne
2
bat
man

YES
YES
NO

Explanation:

Let $Y$ denote the concatenation of names of all the children, and $X$ denote the concatenation of the names of the parents.

Case 1: Here $X$ = "tommarvoloriddle", and $Y$ = "lordvoldemort". Consider $Z$ = "iamlordvoldemort". It is not difficult to see that $Z$ is a permutation of $X$ and $Y$ is a substring of $Z$. Hence $Y$ is a substring of a permutation of $X$, so the answer is "YES".

Case 2: Here $X$ = "cheapup", and $Y$ = "heapcup". Since $Y$ in itself is a permutation of $X$, and as every string is a substring of itself, $Y$ is a substring of $X$ and also a permutation of $X$. Hence "YES".

Case 3: Here $X$ = "brucewayne", and $Y$ = "batman". As "t" is not present in $X$, "t" wont be present in any permutation of $X$, hence the answer is "NO".

Try solving the problem on your own before going to the solution, and before the explanation part first try to understand the code.

Implementation:-

    #include <bits/stdc++.h>

using namespace std;

int main() {

    // your code goes here

    int t;

    cin>>t;

    while(t){

        string father,mother;

        cin>>father>>mother;

        int f_size=father.size();

        int m_size=mother.size();

       

        int no_of_children;

        cin>>no_of_children;

        vector<string> childrens(no_of_children);

        vector<int> parents(123,0),children(123,0);

        for(int i=0;i<no_of_children;i++){

            cin>>childrens[i];

        }

        for(int i=0;i<f_size;i++){

            //Converting char to int

            int num=father[i];

            parents[num]+=1;

        }

        for(int i=0;i<m_size;i++){

            int num=mother[i];

            parents[num]+=1;

        }

        // Now just access the childrens vector so that we can access the names of the

        // childrens respectively

        int is_no1=false;

        for(int j=0;j<no_of_children;j++){

            // Here childrens is a vector array, and children is vector containing the

            // frequency of characters

            string current_child=childrens[j];

            int is_no=false;

            // Now access the name of the current child

            for(int i=0;i<current_child.size();i++){

                int num=current_child[i];

                children[num]+=1;

                if(children[num]>parents[num]){

                    cout<<"NO"<<endl;

                    is_no=true;

                    break;

                }

            }

            if(is_no==true){

                is_no1=true;

                break;

            }

        }

           

        if(is_no1==true){

         

        }

        else{

            cout<<"YES"<<endl;

        }

        t--;

    }

    return 0;

}

Explanation:-

Simply, the problem asks if the concatenation of the names of parents, that is a string, is that the parent of the children strings?

Means the children strings should be made from the parent strings like, from tacmac(suppose a concatenated parent string) we can make cat and cam as the children, as you can see we are just dealing with jumbled words. So the main logic is that the children strings should have all the characters' frequencies either less than or equal to their frequencies in the children strings. If this condition is not met then we can clearly say that there was something else that was included in the production of a children. Means that child is not belonging to the parents mentioned. That sounds a bit awkward, but yeah that's the logic...

Thanks!