Group Anagrams

---

Group Anagrams: 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, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

---

Example 2:

Input: strs = [""]
Output: [[""]]

---

Example 3:

Input: strs = ["a"]
Output: [["a"]]

---

Constraints:

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

---

Try this Problem on your own or check similar problems:

1. Valid Anagram
2. Find Resultant Array After Removing Anagrams
3. Count Anagrams

Solution:

Java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for(String str: strs){
            groups.computeIfAbsent(createKey(str), k -> new ArrayList<String>()).add(str);
        }
        return new ArrayList(groups.values());
    }

    private String createKey(String str){
        StringBuilder sb = new StringBuilder();
        int[] freqMap = new int[26];
        for(char c: str.toCharArray()) ++freqMap[c - 'a'];
        for(int i = 0; i < freqMap.length; ++i){
            if(freqMap[i] != 0) sb.append(freqMap[i]).append((char) i);
        }

        return sb.toString();
    }
}

JavaScript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const groups = new Map();

  for (const str of strs) {
    const key = createKey(str);
    groups.set(key, [...(groups.get(key) || []), str]);
  }

  return Array.from(groups.values());
};

function createKey(str) {
  const freqMap = new Array(26).fill(0);

  for (const c of str) {
    ++freqMap[c.charCodeAt() - "a".charCodeAt()];
  }

  let key = "";
  for (let i = 0; i < freqMap.length; ++i) {
    if (freqMap[i] !== 0) {
      key += freqMap[i] + String.fromCharCode("a".charCodeAt() + i);
    }
  }

  return key;
}

Python

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
      def createKey(s):
        freqMap = [0] * 26

        for c in s:
            freqMap[ord(c) - ord('a')] += 1

        key = ''
        for i in range(len(freqMap)):
            if freqMap[i] != 0:
                key += str(freqMap[i]) + chr(ord('a') + i)

        return key

      groups = {}

      for s in strs:
          key = createKey(s)
          groups.setdefault(key, []).append(s)

      return list(groups.values())

C++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;

        for (const string& str : strs) {
            string key = createKey(str);
            groups[key].push_back(str);
        }

        vector<vector<string>> result;
        for (const auto& group : groups) {
            result.push_back(group.second);
        }

        return result;
    }

    string createKey(const string& str) {
        vector<int> freqMap(26, 0);

        for (char c : str) {
            ++freqMap[c - 'a'];
        }

        string key;
        for (int i = 0; i < freqMap.size(); ++i) {
            if (freqMap[i] != 0) {
                key += to_string(freqMap[i]) + static_cast<char>('a' + i);
            }
        }

        return key;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(nl) where n is number of strings in strs and l is the average (or maximum) length of a string inside the input array
• Space Complexity: O(nl)

---

Explanation:

We will need at most O(n) space for storing the group in case where none of the string is actually an anagram and they all form a seperate group and since for each string we're creating stringbuilder we have to account for that too so the total space complexity is O(nl). We also have the same time complexity, since we traverse the whole strs array and it costs us l to createKey and to hash it to the map. Since anagrams have the same character count, we can use that to create unique group hashing key by appending the count of characters followed by the character (e.g. 3a2b for a string aaabb), then the all anagrams will be hashed with the same key and we can place them in their corresponding group. We finally return the groups by converting map values to a list.