LC #49: Group Anagrams

🧠 Problem Statement

Given an array of strings, group the anagrams together. Return the grouped anagrams as a list of lists.

📎 Leetcode Link

Group Anagrams – Leetcode #49

---

💡 Intuition

Anagrams share the same characters. If you sort their letters, they become identical. So, we can bucket words based on their sorted version.

---

💥 Brute Force (Don't do this)

• Compare each string with every other using isAnagram(s, t) (a utility method inspired from Valid Anagram solution)
• And store string accordingly in a list of lists
• Too slow for large inputs → O(n² * k)

---

⚡ Optimized Approach: Sorting as Key

• ✅ Sort the characters of each word
• ✅ Use the sorted string as a key in a HashMap
• ✅ Group words into the list mapped to that key

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {

        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);

            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }

        return new ArrayList<>(map.values());
    }
}

• Time: O(n * k log k) → n = num of words, k = avg word length
• Space: O(n * k) → for storing map buckets

---

⚡ Even More Optimized (But Not As Readable) Approach

Instead of sorting each word (O(k log k)), we can use a faster trick:

• ✅ Count the frequency of each character using int[26]
• ✅ Convert this frequency array into a string key
• ✅ Group words in the map using that key

for (String s : strs) {
    int[] count = new int[26];
    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }

    StringBuilder sb = new StringBuilder();
    for (int freq : count) {
        sb.append(freq).append('#');
    }

    String key = sb.toString();

    if (!map.containsKey(key)) {
        map.put(key, new ArrayList<>());
    }
    map.get(key).add(s);
}

⚠️ Delimiter '#' is important — avoids merging counts like "1#10" vs "11"

✅ Time: O(n * k) — faster than sorting

❗ Key becomes less readable (looks like a hash string), but grouping logic still works perfectly

---

🧪 Test Cases + Dry Run

✅ Main Test Case 1

Input: ["eat", "tea", "ate"]

🔁 Dry Run

➡️ Output: [["eat", "tea", "ate"]]

---

✅ Main Test Case 2

Input: ["bat", "tab", "tan", "nat"]

🔁 Dry Run

➡️ Output: [["bat", "tab"], ["tan", "nat"]]

---

⚠️ Edge Case 1 – Single Empty String

Input: [""]

🔁 Dry Run

➡️ Output: [[""]]

---

⚠️ Edge Case 2 – Multiple Empty Strings

Input: ["", ""]

🔁 Dry Run

➡️ Output: [["", ""]]

---

🧠 Key Insights & Gotchas

• ✅ Initially thought of isAnagram() + compare with keys → O(n²) → Not optimal
• ✅ Sorting each word works well → O(k log k)
• ⚡ Faster alt: use int[26] frequency count as key (less readable though)
• ❗ new String(char[]) is key → not arr.toString()
• ✅ new ArrayList<>(map.values()) gives final output

---

⛓️ Similar Problems

• Find All Anagrams in a String – LC #438
  ↪ Instead of grouping words, slide a window over a string and check if the current window is an anagram of a pattern (freq count matches)

• Valid Anagram – LC #242
  ↪ Basic version: check if two words are anagrams using sorting or char counts

• Group Shifted Strings – LC #249
  ↪ Group words with the same shifting pattern (e.g., "abc" → "bcd") using offset diff logic

---

🔚 TL;DR

• Group words by their sorted form
• Map from sorted key → original words
• Avoid extra comparisons — sorting is the only grouping logic needed