🧩 Problem Summary
Given an array of strings, group the anagrams together.
Anagram: A word formed by rearranging the letters of another word (e.g., "eat" → "tea", "ate").
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
🧠 Key Idea
Sort each string to generate a canonical form that represents its anagram group.
Use a hash map to group strings with the same sorted form.
✅ Code Explanation (Java)
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String item : strs) {
char[] charArray = item.toCharArray();
Arrays.sort(charArray); // Sort the characters in the string
String s = new String(charArray); // Use the sorted string as the key
List<String> list = map.getOrDefault(s, new ArrayList<>());
list.add(item);
map.put(s, list);
}
return new ArrayList<>(map.values()); // Return grouped anagrams
}
}⏱ Time & Space Complexity
Time Complexity:
Sorting each string takes O(K log K), where K is the string length
Total: O(N * K log K), where N is the number of strings
Space Complexity: O(N * K) to store the hash map and result
🪄 Alternative Approach
Instead of sorting, we can use a character frequency count (array of size 26) to represent each string, which avoids the O(K log K) cost of sorting.
Example key: "1#0#0#1#..." (number of occurrences of each character)
📝 Takeaways
Sorting helps identify anagram groups via a unique signature.
HashMap with String -> List<String> is a powerful tool for grouping.
getOrDefault() is a clean and safe way to retrieve or initialize list values.