Why it works
- Anagrams have the same letters in another order. Put the letters in alphabetical order and all anagrams turn into one string: "arc" and "car" both become "acr". That string is the key.
- The map finds the group of a key at once, so one pass over the words is enough: no word is compared with every other.
- A word whose key is new opens its own group. "rat" has no anagram here, so its group holds it alone.
Complexity
Time O(n · k log k): n words, and the letters of each word, k of them, are sorted. Counting the 26 letters instead of sorting makes the key in O(k). Memory O(n · k): every word goes into the map once.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗