Problem is given two strings, check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be different. For example, “act” and “tac” are anagram of each other.
Input: The first line of input contains an integer T denoting the number of test cases. Each test case consist of two strings in 'lowercase' only, in a single line.
Output: Print "YES" without quotes if the two strings are anagram else print "NO".
Constraints: 1 ≤ T ≤ 30 1 ≤ |s| ≤ 10^16
Example: Input: 1 allergy allergic
Output: NO
My approach is to first check the length of strings, if they are not equal then simply print out NO and if they are equal then sort the strings and then compare element wise.
I am getting correct output on some simple inputs but not on complex ones as my code is not able to pass all the test cases.I am not able to figure out my mistake.
#include <iostream>
using namespace std;
#include<string>
#include<algorithm>
int main() {
int n, t=0;
cin>>n;
for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
cout<<"\n";
if(a.length()!=b.length())
{
cout<<"NO";
}
else
{
sort(a.begin(),a.end());
sort(b.begin(),b.end());
for(int i=0;i<a.length();i++)
{
if(a[i]!=b[i])
{
cout<<"NO";
break;
}
t++;
}
if(t==a.length())
{
cout<<"YES";
}
}
}
return 0;
}
You code seems to give only 1 response when 2 expected.
Problem is that you don't reset your t variable ;) So it is always incrementing.
Example of run: https://ideone.com/IYK6Ad
Input test:
2
aab baa
a a
Output:
YES
Fixed code:
#include <iostream>
using namespace std;
#include<string>
#include<algorithm>
int main() {
int n, t=0;
cin>>n;
for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
if(a.length()!=b.length())
{
cout<<"NO\n";
}
else
{
sort(a.begin(),a.end());
sort(b.begin(),b.end());
if(a != b)
{
cout<<"NO\n";
}
else
{
cout<<"YES\n";
}
}
}
return 0;
}
Some hints about improvement of this algorithm. For now we consider only 1 test case for checking anagram.
So in your case you have 2 * O(n * log n) complexity mainly because of std::sort(Check complexity)
Check for different size is some kind of corner case aka. quick win. So you can keep it but probably testing program will not use those ;)
Does it pass of course will be impacted on how big test cases would be and how many test cases.
Idea of improvement:
std::map<char,int> for that but accessing elements in map takes some time also. So in our case we know something about input data so we can benefit from it. It should be ASCII data so we can fit in fixed array.)For such solution we would get O(n+m) + O(min(n,m)) where n is length of string a and m is length of b. Pretty better complexity.
Example:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
std::vector<int> aCountOfChars(256, 0);
std::vector<int> bCountOfChars(256, 0);
for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
std::vector<int> aCountOfChars(256, 0);
std::vector<int> bCountOfChars(256, 0);
for(int i=0;i<a.size();++i)
{
++aCountOfChars[a[i]];
}
for(int i=0;i<b.size();++i)
{
++bCountOfChars[b[i]];
}
if(aCountOfChars == bCountOfChars)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
}
return 0;
}
Some test cases to check:
7
a b
aab baa
a a
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa b
aabba bbaaa
act tac
allergy allergic