Group Anagrams

How it works

Instead of sorting each string, we can represent every string by the frequency of its characters. Since the problem uses lowercase English letters, a fixed-size array of length 26 can capture how many times each character appears. Two strings are anagrams if and only if their frequency arrays are identical. By using this frequency array (converted to a tuple so it can be a dictionary key), we can group all strings that share the same character counts.

Steps

1. Create a hash map where each key is a 26-length tuple representing character frequencies, and each value is a list of strings belonging to that anagram group.
2. For each string in the input:
   • Initialize a count array of size 26 with all zeros.
   • For each character c in the string, increment the count at the corresponding index.
   • Convert the count array to a tuple and use it as the key.
   • Append the string to the list associated with this key.
3. After processing all strings, return all the lists stored in the hash map.

Complexity

• Time complexity: O(m * n)
• Space complexity:
  • O(m) auxiliary space, excluding the returned output.
  • O(m * n) total space if the output groups are counted.

Where m is the number of strings and n is the length of the longest string.

Things to watch for

Using a Mutable Key Type for the Hash Map

When using character frequency arrays as keys, you must convert them to an immutable type (like a tuple in Python or a string in other languages). Lists and arrays are mutable and cannot be used as dictionary keys directly.

Assuming Input Contains Only Lowercase Letters

The frequency array approach with size 26 only works for lowercase English letters. If the input could contain uppercase letters or other characters, the solution would fail or produce incorrect groupings.

Creating a New Key Format That Has Collisions

When converting frequency counts to strings, using a naive format like concatenation without separators can cause collisions. For example, counts [1,11] and [11,1] could produce the same string "111".

from typing import List
from collections import defaultdict

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

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> res;
        for (const auto& s : strs) {
            vector<int> count(26, 0);
            for (char c : s) {
                count[c - 'a']++;
            }
            string key = to_string(count[0]);
            for (int i = 1; i < 26; ++i) {
                key += ',' + to_string(count[i]);
            }
            res[key].push_back(s);
        }
        vector<vector<string>> result;
        for (const auto& pair : res) {
            result.push_back(pair.second);
        }
        return result;
    }
};