The O(n) Club: Anagrams Don’t Sort Themselves (But You Can Make Them Try)

The O(n) Club: Anagrams Don’t Sort Themselves (But You Can Make Them Try)

⚡ TL;DR

Grab all the strings that are anagrams, put them in the same bucket. Most folks sort every single word (yawn). Smart folks count letters and hash that. Both legit, but there’s a speed king. Here’s the classic, slightly lazy Java:

// Cheap and cheerful: sort-and-group
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    String key = new String(arr);
    map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}

🧠 How Devs Usually Mess This Up

Most folks just sort the word, pray, and call it the day. If your words are short, sure. But crank up the length? You’re now hosting a sorting marathon. Bonus goof: using arrays or mutable objects as HashMap keys in Java. You’ll debug until you’ve forgotten your own name.

🔍 What’s Actually Going On

Imagine an algorithm nightclub where only people with the exact same set of letters on their coats get to sit together. You could force everyone to reorder their clothes alphabetically – like school picture day – but that takes effort. Or, you could just count each letter and tally it up on a checklist. Those with identical tallies? Anagram twins. Sorting is neat, counting is faster. Subtle flex for interviews: use counting. It’s O(NK) instead of O(NK log K) for all you algorithm hipsters.

🛠️ PseudoCode

• Initialize HashMap: key is the group reference (sorted word or character tally string), value is the word group.
• For every word:
  • If using sort: alphabetize the chars, join to make key.
  • If using count: build a size-26 array counting each letter, squash into a string key.
  • Add the original word to the corresponding group in the map.
• Return all the bucketed groups (map values).

// Sorted key approach
for each word w in words:
    key = sort(w)
    map[key].append(w)
 // Count-tally key approach
for each word w in words:
    arr = int[26]
    for char c in w: arr[c-'a']++
    key = join(arr, '#')
    map[key].append(w)

💻 The Code

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) sb.append(cnt[i]).append('#');
        String key = sb.toString();
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Only lowercase? If you sneak in capital letters or non-English, fix your count array size—and indexing math.
• Input order? Output group ordering isn’t guaranteed. Don’t promise anything to your frontend devs.
• Sorting ain’t free: For super-long words, counting rocks. It’s fast and doesn’t make your CPU sad.
• Key key key: Arrays can’t be HashMap keys (Java just won’t). Use a string as your group key—always.

Time/Space: Sorting: O(NK log K). Counting: O(NK). Space? Like your input, but more… grouped.

🧠 Interviewer Brain-Tattoo

Sorting is for humans; hashmaps are for people who want to finish interviews before the coffee runs out.