2025-08-27

49. Group Anagram

Give a list of string group the anagrams together

Solution

• First thought and the brute force is the just sort the strings. Then the anagrams will become the same. The just create a hashmap from the sorted strings and use the index to grab the original string

Time complexity -> We are just doing one pass over the array But we have to sort the strings Space complexity -> Only one hash map

We can’t convert them to numbers and add them up. This is not unique my problem here is how to hash them. Find some function that is fast that takes the strings and produces some output such that hash(f(str)) = hash(f(str2)) if str and str2 are anagrams

One such func is the sorting function but that is O(nlogn) So if we assume that the average sorting complexity is O(mlogm) where m is the average length of the string, then the total complexity will become O(nmlogm). If each string is as big as the list then that would become quadratic

• 0 <= strs[i].length <= 100 This is given. So we can assume that m is 100 Time complexity now become O(100nlog100) which just becomes O(n)

dict_ = {}
for idx, el in enumerate(strs):
	key = "".join(sorted(el))
	dict_.setdefault(key, []).append(el)
return [val for val in dict_.values()]

Better Solution

Without sorting we can use a bit more space and turn the strings into a frequency map of letters? Have an array from 0 to 25 and increment each time you see a char. Join them using “,” and use that string to hash