Group Anagrams

Medium Arrays & Hashing Hashing Original on LeetCode

Group Anagrams is a medium arrays & hashing problem solved with the hashing pattern. The best approach, optimal (letter counts as key), runs in O(n · k) time and O(n · k) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given an array of lowercase words strs. Put the words into groups so that two words share a group exactly when one is an anagram of the other, meaning it uses the same letters the same number of times, just rearranged.

Return the list of groups. The groups, and the words inside each group, can be in any order.

Examples

Example 1

Input: strs = ["stop", "pots", "meal", "tops", "male", "cat"]
Output: [["stop", "pots", "tops"], ["meal", "male"], ["cat"]]
Why: stop, pots and tops use the letters o, p, s, t; meal and male use a, e, l, m; cat has no partner.

Example 2

Input: strs = ["", "b", ""]
Output: [["", ""], ["b"]]
Why: The two empty strings are anagrams of each other.

Example 3

Input: strs = ["abc"]
Output: [["abc"]]
Why: A single word forms a group by itself.

Constraints

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force	`O(n² · k)`	`O(n · k)`
Better (sorted word as key)	`O(n · k log k)`	`O(n · k)`
Optimal (letter counts as key)	`O(n · k)`	`O(n · k)`

1Brute force

TimeO(n² · k)Up to n² / 2 pairs are compared, each in O(k) for words of length k.

SpaceO(n · k)The answer stores every word; the flags take O(n).

Take the first word that has no group yet, start a new group with it, and compare it with every later ungrouped word using letter counts. Every word that matches joins the group.

Keep a used[] flag per word.
For each unused i: start a group with strs[i] and mark it used.
For each unused j > i: if strs[i] and strs[j] have the same letter counts, add strs[j] and mark it used.
Add the group to the answer.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int n = strs.length;
        boolean[] used = new boolean[n];
        List<List<String>> groups = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            List<String> group = new ArrayList<>();
            group.add(strs[i]);
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && sameLetters(strs[i], strs[j])) {
                    used[j] = true;
                    group.add(strs[j]);
                }
            }
            groups.add(group);
        }
        return groups;
    }

    private boolean sameLetters(String a, String b) {
        if (a.length() != b.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < a.length(); i++) {
            count[a.charAt(i) - 'a']++;
            count[b.charAt(i) - 'a']--;
        }
        for (int c : count) if (c != 0) return false;
        return true;
    }
}

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        n = len(strs)
        used = [False] * n
        groups = []
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            group = [strs[i]]
            for j in range(i + 1, n):
                if not used[j] and self.same_letters(strs[i], strs[j]):
                    used[j] = True
                    group.append(strs[j])
            groups.append(group)
        return groups

    def same_letters(self, a: str, b: str) -> bool:
        if len(a) != len(b):
            return False
        count = [0] * 26
        for x, y in zip(a, b):
            count[ord(x) - ord('a')] += 1
            count[ord(y) - ord('a')] -= 1
        return all(c == 0 for c in count)

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();
        vector<bool> used(n, false);
        vector<vector<string>> groups;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            vector<string> group = {strs[i]};
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && sameLetters(strs[i], strs[j])) {
                    used[j] = true;
                    group.push_back(strs[j]);
                }
            }
            groups.push_back(group);
        }
        return groups;
    }

private:
    bool sameLetters(const string& a, const string& b) {
        if (a.size() != b.size()) return false;
        int count[26] = {0};
        for (size_t i = 0; i < a.size(); i++) {
            count[a[i] - 'a']++;
            count[b[i] - 'a']--;
        }
        for (int c : count) if (c != 0) return false;
        return true;
    }
};

function groupAnagrams(strs) {
    const n = strs.length;
    const used = new Array(n).fill(false);
    const groups = [];
    const sameLetters = (a, b) => {
        if (a.length !== b.length) return false;
        const count = new Array(26).fill(0);
        for (let i = 0; i < a.length; i++) {
            count[a.charCodeAt(i) - 97]++;
            count[b.charCodeAt(i) - 97]--;
        }
        return count.every(c => c === 0);
    };
    for (let i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;
        const group = [strs[i]];
        for (let j = i + 1; j < n; j++) {
            if (!used[j] && sameLetters(strs[i], strs[j])) {
                used[j] = true;
                group.push(strs[j]);
            }
        }
        groups.push(group);
    }
    return groups;
}

2Better (sorted word as key)

TimeO(n · k log k)Each of the n words of length k is sorted once.

SpaceO(n · k)The map stores every word and one key per group.

All anagrams turn into the same string when their letters are sorted. Use that sorted string as a key in a hash map from key to the list of words, then return the map's lists.

Create a map from sorted key to list of words.
For each word: sort its characters to get the key and append the word to map[key].
Return all lists in the map.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String word : strs) {
            char[] letters = word.toCharArray();
            Arrays.sort(letters);
            String key = new String(letters);
            groups.computeIfAbsent(key, x -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }
}

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for word in strs:
            key = "".join(sorted(word))
            groups.setdefault(key, []).append(word)
        return list(groups.values())

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        for (const string& word : strs) {
            string key = word;
            sort(key.begin(), key.end());
            groups[key].push_back(word);
        }
        vector<vector<string>> result;
        for (auto& entry : groups) result.push_back(entry.second);
        return result;
    }
};

function groupAnagrams(strs) {
    const groups = new Map();
    for (const word of strs) {
        const key = word.split("").sort().join("");
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(word);
    }
    return [...groups.values()];
}

3Optimal (letter counts as key)

TimeO(n · k)Each word is scanned once; the key has a fixed 26 parts.

SpaceO(n · k)The map stores every word and one key per group.

Skip the sort. Count how many times each of the 26 letters appears and turn the counts into a key such as "1#0#2#…". Anagrams produce identical counts, so they land in the same bucket, and building the key is linear in the word length.

Create a map from count key to list of words.
For each word: fill count[26], join the counts with a separator to form the key.
Append the word to map[key].
Return all lists in the map.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String word : strs) {
            int[] count = new int[26];
            for (int i = 0; i < word.length(); i++) count[word.charAt(i) - 'a']++;
            StringBuilder key = new StringBuilder();
            for (int c : count) key.append(c).append('#');
            groups.computeIfAbsent(key.toString(), x -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }
}

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for word in strs:
            count = [0] * 26
            for ch in word:
                count[ord(ch) - ord('a')] += 1
            groups.setdefault(tuple(count), []).append(word)
        return list(groups.values())

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

function groupAnagrams(strs) {
    const groups = new Map();
    for (const word of strs) {
        const count = new Array(26).fill(0);
        for (let i = 0; i < word.length; i++) count[word.charCodeAt(i) - 97]++;
        const key = count.join("#");
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(word);
    }
    return [...groups.values()];
}

Edge cases to test

Empty strings, which all belong to one group
The same word repeated: duplicates stay in the group
Words with the same letters but different counts, like "aab" and "abb", are not anagrams
No two words are anagrams: every group has one word

Hints

Hint 1

Two words are anagrams exactly when they have the same letters with the same counts. What single value could describe that?

Hint 2

Sorting a word's letters gives the same string for all its anagrams. Use it as a hash map key.

Hint 3

Sorting costs O(k log k). A count of each of the 26 letters is also a key and takes only O(k) to build.

FAQ

What is the best time complexity for Group Anagrams?

Optimal (letter counts as key) runs in O(n · k) time and O(n · k) extra space. Each word is scanned once; the key has a fixed 26 parts.

Which pattern does Group Anagrams use?

It is a arrays & hashing problem that uses the hashing pattern.

Is there a brute force solution for Group Anagrams?

Yes. Brute force takes O(n² · k) time and O(n · k) space. Take the first word that has no group yet, start a new group with it, and compare it with every later ungrouped word using letter counts.

Which edge cases should I test for Group Anagrams?

Empty strings, which all belong to one group; The same word repeated: duplicates stay in the group; Words with the same letters but different counts, like "aab" and "abb", are not anagrams; No two words are anagrams: every group has one word.