Group anagrams | Leetcode #49

This video explains a very important interview problem which has already been asked in many big MNCs like microsoft,amazon,google,facebook etc. The problem says that given an array of strings, we need to group them such that strings in a group must be anagrams of each other. I have explained using 3 methods with code. It makes use of hashmap and hashmap of hashmap for optimal solution. CODE LINK is given below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[aaryanchaturvedi]

Those two words "eat" "bat" hurts differently now, if you know what i mean !!!

[alaminhossain]

You can't explain more better than this, You deserve an award.

[syedyaser]

The third approach can be further optimised by using integer as the hash key. As we have max 26 char, we can represent the hash as an integer. Iterate over the chars of the word and set the particular position bit in the integer and at the end use this integer as key/bucket in the map. Your map syntax would look something like this.
Map<Integer, List<String>>

[deepalipatil]

Tons of thanks for such a precise explanation. No one can teach better than this. Hats off

[samirpaul]

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
strDic = {}

for s in strs:
arr = [0]*26
for i in s:
arr[ord(i)-97] += 1

# As arr is an array and we can not use an array as a key of dictionary so make arr a tuple
key = tuple(arr)
if key not in strDic:
strDic[key] = [s]
else:
strDic[key] += [s]

res = []
for key in strDic:
res.append(strDic[key])

return res

[voldemort]

Sir 3rd method time Complexity will be approximatly equal to 2nd method as to implement 3rd method we will use map, as we cannot use unordered_map inside unordered_map

So time for third is Time - O(N * (M*log(N) + logN))

[nikhilmane]

2nd approach

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {

vector<vector<string>> ans;

map<map<char, int>, vector<string>> mp;
int n = strs.size();
string temp;

for(int i=0;i<n;i++)
{
map<char, int> temp;
for(char c:strs[i]){
temp[c]++;
}

mp[temp].push_back(strs[i]);
}


for(auto
{
ans.push_back(itr->second);
}

return ans;



}
};

you are welcome !

[gurusivaram]

I was trying to solve this problem since yesterday night. But when I came to know about map, Its just a matter of a min to solve that one... Thank you TECH DOSE... God bless you...🙌🏻🙌🏻🙌🏻🙌🏻🙌🏻

[spetsnaz_]

We can sort the temp string and not the original string so that the original string does not change if we have this constraint

[symbol]

I cannot believe this is a medium... graph problems I find are easier than this nonsense problem...

[ShubhamMishra-mzzw]

One of the best explanation for this problem. Thank you sir

[ksansudeen]

Hi, Thanks for this video.. i was stuck with below input ["", ""]. the expected outcome is [["", ""]].
but in map since the empty string will be repeating the output im getting is [[""]]. i can handle for this edge case if string is empty, but pls advise if we can have better way.

[ivanleon]

why do you sort the stri[i] instead of the temp string? why do you prefer to modify the input instead of a temporary variable?

[saigopalraopeechara]

how come time complexity is o(n*k) when we are using orderedmap in the last optimal approach?

[mohitsaran]

can you share the code of the third most optimised approach without sorting ??
I cannot able to code it properly

[ShreyaSingh-vrqi]

Second approach is awesome, we can also solve this problem using trie data structure

[ridimamittal]

THIS VIDEO IS JUST WOW, THANK YOUUU SOOO MUCH, I WAS NOT ABLE TO UNDERSTAND THIS AFTER HOURS I FIND IT AND IT IS SUCH A RELIEF, THANKS TON!!!!

[offbeat.prince]

Kindly check the time compexity:

vector<vector<string>> groupAnagrams(vector<string>& strs) {
int n = strs.size();
map<vector<int>, vector<string>> ump;
for(int i =0;i < n; i++)
{
string s = strs[i];
vector<int> hsh(26, 0);
for(int j = 0; j < s.length(); j++)
{
hsh[s[j]-'a']++;
}
ump[hsh].push_back(s);

}
vector<vector<string>> ans;
for(auto it: ump)
{
auto temp = it.second;
ans.push_back(temp);
}
return ans;
}

[abhayanandkumar]

Your videos are of different level...thank you so much sir!

[sandeepa]

Very very very well explained brother! Thanks so much.