Optimal Categorization Using Character Frequency Count:
- Use character counts (a tuple of 26 integers) as a canonical hash map key to group anagrams without sorting.
from collections import defaultdict
def group_anagrams(strs: list[str]) -> list[list[str]]:
anagram_map = defaultdict(list)
for word in strs:
count = [0] * 26
for char in word:
count[ord(char) - ord('a')] += 1
anagram_map[tuple(count)].append(word)
return list(anagram_map.values())
Complexity & Key Logic:
- Time Complexity: O(N * K), where N is number of words and K is maximum word length.
- Space Complexity: O(N * K) to store the grouped anagram lists.
- Algorithm Details:
- Anagrams share identical character counts.
- Converting the 26-element frequency array into an immutable tuple allows it to serve as a hash map key.
- Avoids sorting strings (which would take O(N * K log K)), delivering linear performance per string.