Group Anagrams

Sort the letters of each string to get a canonical form — anagrams sort to the same string. Use that sorted string as a hash map key.

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            groups[key].append(s)
        return list(groups.values())

Works, but sorting every one of the n strings costs O(k log k) each (k = max string length), for O(n · k log k) total — more work than necessary just to build a grouping key.

Instead of sorting, count the occurrences of each of the 26 letters directly. Two strings are anagrams exactly when their count arrays match, so a tuple of counts makes an equally valid — and cheaper to compute — hash map key.

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)
        for s in strs:
            counts = [0] * 26
            for ch in s:
                counts[ord(ch) - ord('a')] += 1
            groups[tuple(counts)].append(s)
        return list(groups.values())

Watch each string collapse to a short count key — anagrams produce the same key, so they land in the same group.

Tracing the first example, strs = ["eat", "tea", "tan", "ate", "nat", "bat"] (the key is the 26-slot count tuple, shown condensed as letter-count pairs like a1e1t1):

Correctness: two strings produce the same count tuple if and only if they contain the same letters the same number of times — which is precisely the definition of anagram. Grouping by that key therefore groups exactly the anagrams together, regardless of letter order.

Complexity: building each string’s count array is O(k) (26 fixed increments spread over k characters), done for all n strings — O(n · k) time, better than sorting’s O(n · k log k). Every character across every string ends up stored once in the output groups — O(n · k) space.