# O(MN) time and O(N) space solution.

• N=number of strings, M=average number of chars in each string.

the code is a little bit long, but this uses O(N) space assuming unordered_map uses space linear to the number of keys. Space excludes the space needed for the solution.

Runtime is O(M*N) as each char is processed.

Took ~100ms to be judged.

``````struct key{
int freq[26];
int hash;
bool operator==(const key&k2)const{
int i,j;
if(k2.hash!=hash)return false;
for(i=0;i<26;i++)
if(freq[i]!=k2.freq[i])return false;
return true;
}
};
namespace std{
template<> struct hash<key> {
size_t operator()(const key&k)const {
return k.hash;
}
};
};
typedef unordered_map<key,int> mapt;
class Solution {
public:
key calc(const string&s){
key k={0};
int i,j;
for(i=0;i<s.size();i++){
k.freq[s[i]-'a']++;
}
for(i=0;i<26;i++){
k.hash = k.hash*31 + k.freq[i];
}
return k;
}
vector<string> anagrams(vector<string> &strs) {
int i,j;
vector<string> r;
mapt map;
for(i=0;i<strs.size();i++){
key k=calc(strs[i]);
pair<mapt::iterator,bool> p=map.emplace(make_pair(k,i));
r.emplace_back(strs[i]);
int&idx=(p.first)->second;
if(idx>=0){
r.emplace_back(strs[idx]);
idx = -1;
}
}
}
return r;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.