1. Understanding the Problem

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

For example, if strs = ["eat","tea","tan","ate","nat","bat"], a valid output would be [["bat"],["nat","tan"],["ate","eat","tea"]].

The Core Challenge:

How do we quickly identify if two strings belong to the same anagram group without comparing every string pair directly? We need a canonical key—a standardized representation that is identical for all words that are anagrams of one another.

2. The Standard Approach: Sorting String Keys

The most intuitive way to create a canonical key for any word is to sort its characters alphabetically. For example, sorting "eat", "tea", and "ate" all produce the exact same key: "aet".

We can use a Hash Map where the key is the sorted string, and the value is a list of original words matching that sorted key.

Trade-off Analysis

• Time Complexity: O(N * K log K) — Where N is the number of strings and K is the maximum length of a string. For each of the N strings, we sort K characters taking O(K log K) time.
• Space Complexity: O(N * K) — To store the hash map and the resulting grouped lists.

3. The Optimal Approach: Character Count Tuple/String as Key (O(N * K) Time)

Can we eliminate the logarithmic factor log K from sorting? Yes! Since the input strings consist only of lowercase English letters (a through z), we can represent any word by an array of length 26 storing its character frequencies.

For example, "abbc" becomes a frequency array [1, 2, 1, 0, 0, ..., 0]. Converts of this frequency array (as a tuple or formatted string key) serve as a unique fingerprint for all anagrams of that word.

Because generating a 26-element frequency count takes strictly O(K) time, our overall time complexity drops to O(N * K)!

4. The Logic Step-by-Step

1. Initialize an empty Hash Map (or Dictionary) where keys will be frequency representations and values will be lists of strings.
2. Iterate Through Every String: For each string s in strs:
   • Create a frequency count array/tuple of size 26 initialized to zero.
   • Count occurrences of each character in s by incrementing count[ord(char) - ord('a')].
   • Convert the count array into a hashable key (e.g., a tuple in Python, or a delimiter-separated string like "#1#2#1#0..." in Java/C++).
   • Append the original string s to the list corresponding to that frequency key in the Hash Map.
3. Extract and return all values (lists of grouped anagrams) from the Hash Map.

5. Complexity Analysis

• Time Complexity: O(N * K) — Where N is the total number of strings and K is the maximum string length. Counting characters takes O(K) time per string.
• Space Complexity: O(N * K) — Needed to store the Hash Map keys and the grouped string results.

6. Code Implementations

Expand the sections below to see both the frequency hashing and sorted key implementations across different languages.

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Map character count tuple to list of anagrams
        ans = defaultdict(list)
        
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            # Tuples are hashable and can be used as dictionary keys
            ans[tuple(count)].append(s)
            
        return list(ans.values())

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            
            // Build string key from frequency array
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append('#').append(count[i]);
            }
            String key = sb.toString();
            
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }
        
        return new ArrayList<>(map.values());
    }
}

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
        std::unordered_map<std::string, std::vector<std::string>> map;
        
        for (const std::string& s : strs) {
            std::string key = s;
            std::sort(key.begin(), key.end()); // Using sorted string as key
            map[key].push_back(s);
        }
        
        std::vector<std::vector<std::string>> result;
        for (auto& pair : map) {
            result.push_back(pair.second);
        }
        
        return result;
    }
};

7. Conclusion: You Are Ready

Congratulations! You have mastered Group Anagrams. Designing custom canonical keys—whether by sorting or frequency tuples—is a fundamental technique for equivalence-class categorization problems in computer science. Keep this pattern handy whenever you need to group items based on structural invariance. Keep practicing, and happy coding!