PROBLEM LINK:
Author: mugdha40
Tester: valiant_vidit
Editorialist: mugdha40
DIFFICULTY:
super easy
PROBLEM:
Given a problem word P and evidence word E consisting of lower case English alphabets:
- check if all characters of evidence word E can be found in problem word P or not.
- if a character c occurs x times in E, then P must contain c at least x times
Prerequisites:
- knowledge of strings and loops.
- Simple logic applications.
Hint:
-
A simple brute force logic will satisfy the given constraints.
-
Try by using an array of 26 letters which keeps an eye on characters of problem word and evidence word.
[/details]
QUICK EXPLANATION:
We can proceed with the idea by making an array of size 26 with all elements be 0 initially. This array will help us in checking the frequency of characters in problem word and evidence word. Use a “for each” loop which will traverse over each character of the problem word and fill its frequency in that array. Then use another “for each” loop which will traverse over the evidence word and check if the frequency of each character in the array that matches with the evidence word is greater than or equal to the frequency of characters of the evidence word or not.
EXPLANATION:
First of all, we’ll declare an array ar[26] where each element will denote the frequency of all 26 lowercase English alphabets(i.e 0th position for ‘a’,1st for ‘b’ etc) and set all elements of the array 0 initially.
Then we’ll use a “for each” loop that will traverse over the problem word. Here ar[w-‘a’]++ will go the index of that character and increase its frequency from 0 to 1 (suppose if that character is found again in any of the iterations then the frequency will increase from 1 to 2 and so on).
-
To understand the meaning of ar[w-‘a’]:
Lets say the problem word ( P ) is “btxca” and evidence word ( E ) is “cat”.
So during the first iteration w will be b; now ASCII value of b is 98 and ASCII value of a is 97 so ar[98-97]++ => ar[1]++
this means that the array will change like {0,1,0…} after the first iteration. Similarly, the array will get updated after each iteration and eventually, it will store the frequency of each character of the problem word.
now we’ll use another "for each " loop:-
case 1:- (if all letters of evidence word are not present in problem word)
if the frequency of a particular character of the evidence word is found to be zero in the array then the value of the flag will change from 0 to 1 and the loop will break printing NO in output.
case 2:-(If all characters of evidence word are present in problem word)
The frequency count of that character will obviously be greater than zero and ar[w-‘a’] --will decrease the count indicating that we’ve mapped the character in the evidence word. The flag will remain zero and the program will print YES in the output.
SOLUTIONS:
Setter's Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
string e,p;
cin>>e;
cin>>p;
int ar[26] = {0};
int flag = 0;
for(char w: p)
{
ar[w-'a']++;
}
for(char w: e)
{
if(!ar[w-'a'])
{
cout<<"NO"<<endl;
flag = 1;
break;
}
ar[w-'a']--;
}
if(flag == 0)
cout<<"YES"<<endl;
}
return 0;
}
Tester's Solution
/*author : vidit shukla
(valiant_vidit)*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long int
#define bhaago ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define loop(a,b,i) for(ll i=a;i<b;i++)
#define loop1(a,b,i) for(ll i=a;i>b;i--)
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define endl '\n'
#define Endl '\n'
#define az(i) for(auto it:i)cout<<it<<" ";cout<<Endl;
#define setin(s,i) for(auto it:i)s.insert(it);
#define mpin(mp,i) for(auto it:i)mp[it]++;
#define yy cout<<"YES"<<endl
#define nn cout<<"NO"<<endl
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
const double pi = std::acos(-1);
using namespace std;
const ll mod = 1000000000+7;
//------------------------------------------------------
//---------------------------------------------------
int main() {
//see if tcs are present or not.
bhaago;
// freopen("@iin.txt","r",stdin);
// freopen("@output.txt","w",stdout);
ll tc=1;
cin>>tc;
while(tc--)
{
string s1,s2;
cin>>s1>>s2;
ll arr[26]={0},brr[26]={0},fl=0;
loop(0,s1.size(),i)arr[s1[i]-'a']++;
loop(0,s2.size(),i)brr[s2[i]-'a']++;
loop(0,26,i)if(arr[i]>brr[i]){fl=1;break;}
if(!fl)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
// cout<<n<<endl;
}
// your code goes here
return 0;
}