5. Group Anagrams · DSA Practice

Group the words in strs so that anagrams end up together. Return the groups in any order; words inside a group can be in any order too.

Example 1

Input: strs = ["note","tone","act","cat","stone","onset","tac"]

Output: [["note","tone"],["act","cat","tac"],["stone","onset"]]

Example 2

Input: strs = ["ab","ba","abc","cab","bca","xyz"]

Output: [["ab","ba"],["abc","cab","bca"],["xyz"]]

Constraints

1 ≤ strs.length ≤ 10⁴
0 ≤ strs[i].length ≤ 100

Hint 1

Find a key that is identical for all anagrams: the sorted word, or its letter counts.

Hash TableStringSorting

Approach 1: Sorted-word key

Sort each word’s letters and use it as a hash-map key.

⏱ Time O(n · k log k)💾 Space O(n · k)

Approach 2: Letter-count key ✅

Use the 26 letter counts (as a tuple) as the key, avoiding the sort.

⏱ Time O(n · k)💾 Space O(n · k)

Reference solution for Letter-count key (time O(n · k), space O(n · k)). Each solution passes every test in all four languages.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for w in strs:
            key = [0] * 26                 # letter counts identify an anagram group
            for ch in w:
                key[ord(ch) - 97] += 1
            groups[tuple(key)].append(w)
        return list(groups.values())

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

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        for (const string& w : strs) {
            string key = w;
            sort(key.begin(), key.end());        // sorted letters = group key
            groups[key].push_back(w);
        }
        vector<vector<string>> res;
        for (auto& kv : groups) res.push_back(kv.second);
        return res;
    }
};

function groupAnagrams(strs) {
  const groups = new Map();
  for (const w of strs) {
    const key = [...w].sort().join(''); // sorted letters = group key
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(w);
  }
  return [...groups.values()];
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Arrays, Hashing & Prefix Sums.