Group Anagrams - Leetcode Solution

Problem Link

Step-by-Step Thought Process

Brute Force

Initialize a dictionary to group anagrams.
For each string in the input list:
- Sort the characters in the string.
- Use the sorted string as a key in the dictionary.
- Append the original string to the list corresponding to this key.
Return the values of the dictionary as the result.

Code Solution (Brute Force)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            ans[key].append(s)

        return list(ans.values())
# Time: O(n * (m log m))
# Space: O(n * m)
# n is the number of strings, m is the length of largest string

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

using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> ans;
        for (const string& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            ans[key].push_back(s);
        }
        vector<vector<string>> result;
        for (const auto& entry : ans) {
            result.push_back(entry.second);
        }
        return result;
        // Time: O(n * m log m), n is the number of strings, m is the length of largest string
        // Space: O(n * m)
    }
};

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> ans = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            ans.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(ans.values());
        // Time: O(n * m log m), n is the number of strings, m is the length of largest string
        // Space: O(n * m)
    }
}

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const ans = new Map();
    for (const s of strs) {
        const key = s.split('').sort().join('');
        if (!ans.has(key)) {
            ans.set(key, []);
        }
        ans.get(key).push(s);
    }
    return Array.from(ans.values());
    // Time: O(n * m log m), n is the number of strings, m is the length of largest string
    // Space: O(n * m)
};

Inefficiency

Sorting each string takes O(K log K) time, where K is the length of the string. Doing this for all N strings results in O(NK log K) time complexity.

Optimal Approach

Use a frequency count of letters (array of size 26) as the key instead of sorting.
For each string in the input list:
- Count the frequency of each letter (O(K) time).
- Use the tuple of counts as a key in the dictionary.
- Append the original string to the list corresponding to this key.
Return the values of the dictionary as the result.
Efficiency Gain Avoids the need to sort each string. The time complexity improves to O(NK), where N is the number of strings and K is the maximum length of a string.

Code Solution (Optimal)

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams_dict = defaultdict(list)
        for s in strs: # n
            count = [0] * 26
            for c in s:
                count[ord(c) - ord("a")] += 1
            key = tuple(count)
            anagrams_dict[key].append(s)

        return anagrams_dict.values()
# n is the number of strings, m is the length of largest string
# Time Complexity: O(n * m)
# Space Complexity: O(n * m)

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

using namespace std;

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

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagramsMap = new HashMap<>();
        
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            StringBuilder key = new StringBuilder();
            for (int num : count) {
                key.append('#').append(num);
            }
            String keyStr = key.toString();
            anagramsMap.computeIfAbsent(keyStr, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(anagramsMap.values());
    }
}

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const anagramsMap = new Map();
    
    strs.forEach(s => {
        const count = new Array(26).fill(0);
        for (let c of s) {
            count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        const key = count.join(',');
        if (!anagramsMap.has(key)) {
            anagramsMap.set(key, []);
        }
        anagramsMap.get(key).push(s);
    });
    
    return Array.from(anagramsMap.values());
};

Detailed Explanation

Understanding the Problem: Group Anagrams

The “Group Anagrams” problem asks you to group strings that are anagrams of each other. Two strings are anagrams if they contain the same characters in any order, with the same frequency.

For example, given the input ["eat", "tea", "tan", "ate", "nat", "bat"], the output should be grouped as:

["eat", "tea", "ate"]
["tan", "nat"]
["bat"]

Why This Problem Matters

This problem is widely used to teach the power of hashing and the idea of transforming complex objects into simpler keys. It sharpens your understanding of how to efficiently group data based on custom equivalence logic and is foundational for problems involving classification, normalization, or frequency-based analysis.

Basic Approach: Sort and Group

The simplest way to group anagrams is by sorting each word and using the sorted result as the key. All anagrams, once sorted, will yield the same string. For example:

"eat" → "aet"
"tea" → "aet"
"ate" → "aet"

These will all be grouped under the key "aet".

Steps:

Initialize an empty dictionary anagramGroups.
For each word in the input list:
- Sort the characters in the word (O(K log K), where K is the word length).
- Use the sorted string as the key in the dictionary.
- Append the original word to the value list of that key.
Return all value lists from the dictionary.

Optimization: Use Letter Frequency Instead of Sorting

Sorting each string costs O(K log K), which can be slow for large K. Instead, we can use a frequency count of characters (like a 26-element array for lowercase English letters).

Steps:

Initialize an empty dictionary anagramGroups.
For each string:
- Create a frequency count (array of 26 zeros).
- Increment the count for each character in the word.
- Convert the array to a tuple (since lists aren't hashable) and use that as the key.
- Append the word to the group corresponding to that key.
Return all grouped values.

Efficiency Gain:

Instead of sorting, counting characters takes O(K) per word. This reduces the overall time complexity from O(NK log K) to O(NK), where N is the number of words.

Example Walkthrough

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Using sorted strings:

"eat" → "aet"
"tea" → "aet"
"tan" → "ant"
"ate" → "aet"
"nat" → "ant"
"bat" → "abt"

Final groups:

["eat", "tea", "ate"]
["tan", "nat"]
["bat"]

Time and Space Complexity

Time Complexity:

Using sorting: O(NK log K)
Using frequency counting: O(NK)

Space Complexity: O(NK), since we store N strings each of length up to K, and the dictionary stores grouping information.

Edge Cases to Consider

Empty input list → return []
All strings are identical → one group
All strings are unique with no anagrams → each string in its own group

Conclusion

The “Group Anagrams” problem is a powerful example of classification and grouping using hash maps. It reinforces strategies like character counting and normalization, which are frequently useful in both algorithm design and data preprocessing tasks in the real world.

Get Personalized Support at AlgoMap Bootcamp 💡