# Group Anagrams **Difficulty:** MEDIUM [External](https://leetcode.com/problems/group-anagrams) Canonical: https://scaleengineer.com/dsa/problems/group-anagrams **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Hash Table, String **Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [DoorDash](https://scaleengineer.com/companies/doordash), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [HCL](https://scaleengineer.com/companies/hcl), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Myntra](https://scaleengineer.com/companies/myntra), [Nielsen](https://scaleengineer.com/companies/nielsen), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [PayPal](https://scaleengineer.com/companies/paypal), [Publicis Sapient](https://scaleengineer.com/companies/publicis-sapient), [SAP](https://scaleengineer.com/companies/sap), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [Zoho](https://scaleengineer.com/companies/zoho), [athenahealth](https://scaleengineer.com/companies/athenahealth), [eBay](https://scaleengineer.com/companies/ebay), [persistent systems](https://scaleengineer.com/companies/persistent-systems), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [Coupang](https://scaleengineer.com/companies/coupang), [Dell](https://scaleengineer.com/companies/dell), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Turing](https://scaleengineer.com/companies/turing), [Veeva Systems](https://scaleengineer.com/companies/veeva-systems), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [BlackRock](https://scaleengineer.com/companies/blackrock), [Disney](https://scaleengineer.com/companies/disney), [PhonePe](https://scaleengineer.com/companies/phonepe), [Wayfair](https://scaleengineer.com/companies/wayfair), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Niantic](https://scaleengineer.com/companies/niantic), [HashedIn](https://scaleengineer.com/companies/hashedin), [Twilio](https://scaleengineer.com/companies/twilio), [Anduril](https://scaleengineer.com/companies/anduril), [Splunk](https://scaleengineer.com/companies/splunk), [Texas Instruments](https://scaleengineer.com/companies/texas-instruments), [NetApp](https://scaleengineer.com/companies/netapp), [Sigmoid](https://scaleengineer.com/companies/sigmoid), [Workday](https://scaleengineer.com/companies/workday), [Affirm](https://scaleengineer.com/companies/affirm), [BP](https://scaleengineer.com/companies/bp), [Compass](https://scaleengineer.com/companies/compass), [Faire](https://scaleengineer.com/companies/faire), [MSCI](https://scaleengineer.com/companies/msci), [Paycom](https://scaleengineer.com/companies/paycom), [Qualtrics](https://scaleengineer.com/companies/qualtrics), [Ripple](https://scaleengineer.com/companies/ripple), [Smartsheet](https://scaleengineer.com/companies/smartsheet), [Verily](https://scaleengineer.com/companies/verily), [Whatnot](https://scaleengineer.com/companies/whatnot) --- ## Problem Given an array of strings `strs`, group the anagrams together. You can return the answer in **any order**. **Example 1:** **Input:** strs = \["eat","tea","tan","ate","nat","bat"\] **Output:** \[\["bat"\],\["nat","tan"\],\["ate","eat","tea"\]\] **Explanation:** * There is no string in strs that can be rearranged to form `"bat"`. * The strings `"nat"` and `"tan"` are anagrams as they can be rearranged to form each other. * The strings `"ate"`, `"eat"`, and `"tea"` are anagrams as they can be rearranged to form each other. **Example 2:** **Input:** strs = \[""\] **Output:** \[\[""\]\] **Example 3:** **Input:** strs = \["a"\] **Output:** \[\["a"\]\] **Constraints:** * `1 <= strs.length <= 104` * `0 <= strs[i].length <= 100` * `strs[i]` consists of lowercase English letters. # Approaches ## Brute Force with Anagram Check This approach involves comparing every string with every other string in the array. For each pair, we check if they are anagrams. We use an auxiliary boolean array to keep track of strings that have already been grouped to avoid redundant checks and processing. **Time:** O(N^2 * K log K) · **Space:** O(N*K) **Pros:** Conceptually simple and easy to understand. **Cons:** Very high time complexity, making it impractical for large inputs.; Will likely result in a Time Limit Exceeded (TLE) error on most online judges for the given constraints. ### Explanation We iterate through the input array `strs`. For each string `strs[i]`, we start a new group. We then iterate through the rest of the array (`j` from `i+1` to `n-1`). For each `strs[j]`, we check if it's an anagram of `strs[i]`. To check for anagrams, we can sort both strings and see if the sorted versions are equal. A `visited` array is used to mark strings that have been placed into a group, so they are not considered again as the starting point of a new group. This method is straightforward but highly inefficient due to the nested loops and repeated anagram checks. ```java import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public List> groupAnagrams(String[] strs) { if (strs == null || strs.length == 0) { return new ArrayList<>(); } List> result = new ArrayList<>(); boolean[] visited = new boolean[strs.length]; for (int i = 0; i < strs.length; i++) { if (!visited[i]) { List currentGroup = new ArrayList<>(); currentGroup.add(strs[i]); visited[i] = true; for (int j = i + 1; j < strs.length; j++) { if (!visited[j] && isAnagram(strs[i], strs[j])) { currentGroup.add(strs[j]); visited[j] = true; } } result.add(currentGroup); } } return result; } private boolean isAnagram(String s1, String s2) { if (s1.length() != s2.length()) { return false; } char[] arr1 = s1.toCharArray(); char[] arr2 = s2.toCharArray(); Arrays.sort(arr1); Arrays.sort(arr2); return Arrays.equals(arr1, arr2); } } ``` ### Algorithm - Initialize an empty list of lists `result` and a boolean array `visited` of size `n` (length of `strs`). - Loop through each string `strs[i]` from `i = 0` to `n-1`. - If `strs[i]` has not been visited (`visited[i]` is false): - Create a new list `currentGroup` and add `strs[i]` to it. - Mark `visited[i]` as true. - Loop through the remaining strings `strs[j]` from `j = i+1` to `n-1`. - If `strs[j]` has not been visited and is an anagram of `strs[i]`: - Add `strs[j]` to `currentGroup`. - Mark `visited[j]` as true. - Add `currentGroup` to the `result`. - Return `result`. ## Grouping with Sorted Strings as Keys A more efficient approach is to realize that all anagrams of a string become identical when their characters are sorted. We can use this sorted string as a canonical representation (a key) to group anagrams together in a hash map. **Time:** O(N * K log K) · **Space:** O(N * K) **Pros:** Significantly faster than the brute-force approach.; The logic is clean and relies on a standard data structure (hash map). **Cons:** The time complexity is dominated by sorting each string, which can be slightly less optimal than character counting. ### Explanation We create a hash map where keys are sorted strings and values are lists of original strings that correspond to that sorted key. We iterate through the input array `strs`. For each string, we convert it to a character array, sort the array, and then convert it back to a string. This sorted string serves as the key. We then use this key to add the original string to the corresponding list in the hash map. If the key is not yet in the map, we first create a new empty list for it. After processing all strings, the values of the hash map are the required groups of anagrams. We collect these lists and return them. ```java import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; class Solution { public List> groupAnagrams(String[] strs) { if (strs == null || strs.length == 0) { return new ArrayList<>(); } Map> map = new HashMap<>(); for (String s : strs) { char[] charArray = s.toCharArray(); Arrays.sort(charArray); String key = new String(charArray); if (!map.containsKey(key)) { map.put(key, new ArrayList<>()); } map.get(key).add(s); } return new ArrayList<>(map.values()); } } ``` ### Algorithm - Initialize a hash map `map` where `key` is a `String` and `value` is a `List`. - Iterate through each string `s` in the input array `strs`. - Convert `s` to a character array `charArray`. - Sort `charArray`. - Create a new string `key` from the sorted `charArray`. - Retrieve the list of strings for `key` from the map. If it doesn't exist, create a new list. - Add the original string `s` to this list. - Put the `key` and the updated list back into the map. - After the loop, the map's values will contain the grouped anagrams. - Return a new list constructed from the values of the map. ## Grouping with Character Count as Keys This approach is an optimization over the sorting method. Instead of sorting, we create a canonical key for each string based on its character counts. Two strings are anagrams if and only if they have the same character counts. **Time:** O(N * K) · **Space:** O(N * K) **Pros:** Most efficient time complexity among the three approaches.; Avoids the log K factor associated with sorting. **Cons:** The key generation is slightly more complex than simply sorting the string. ### Explanation We use a hash map, similar to the previous approach. However, the key is generated differently. For each string, we compute its character frequency. Since the strings only contain lowercase English letters, we can use an integer array of size 26 for this. After counting, we need to convert this frequency array into a unique, hashable key. A common way is to create a string representation. For example, an array `[1, 2, 0, ...]` (one 'a', two 'b's) can be converted to a string like `"1#2#0#..."`. We iterate through the input `strs`. For each string `s`, we calculate its character count array. We then build a key string from this count array. This key is used to store the original string `s` in the hash map. Finally, we return the lists of strings from the map's values. This method avoids the `O(K log K)` sorting cost, replacing it with a linear `O(K)` scan. ```java import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class Solution { public List> groupAnagrams(String[] strs) { if (strs == null || strs.length == 0) { return new ArrayList<>(); } Map> map = new HashMap<>(); for (String s : strs) { int[] count = new int[26]; for (char c : s.toCharArray()) { count[c - 'a']++; } StringBuilder sb = new StringBuilder(); for (int i = 0; i < 26; i++) { sb.append('#'); sb.append(count[i]); } String key = sb.toString(); if (!map.containsKey(key)) { map.put(key, new ArrayList<>()); } map.get(key).add(s); } return new ArrayList<>(map.values()); } } ``` ### Algorithm - Initialize a hash map `map` where `key` is a `String` and `value` is a `List`. - Iterate through each string `s` in the input array `strs`. - Create an integer array `count` of size 26, initialized to zeros. - For each character `c` in `s`, increment `count[c - 'a']`. - Build a key string from the `count` array. A simple way is to append each count value preceded by a delimiter (e.g., `#`) to a `StringBuilder`. - Use this generated `key` to store the original string `s` in the map, creating a new list if the key is new. - After iterating through all strings, return a new list containing the values of the map. # Solutions ### Java ```java class Solution { public List> groupAnagrams(String[] strs) { Map> d = new HashMap<>(); for (String s : strs) { char[] t = s.toCharArray(); Arrays.sort(t); String k = String.valueOf(t); d.computeIfAbsent(k, key->new ArrayList<>()).add(s); } return new ArrayList<>(d.values()); } } ``` ### CSharp ```csharp using System.Collections.Generic ; public class Comparer : IEqualityComparer < string > { public bool Equals ( string left , string right ) { if ( left . Length != right . Length ) return false ; var leftCount = new int [ 26 ]; foreach ( var ch in left ) { ++ leftCount [ ch - 'a' ]; } var rightCount = new int [ 26 ]; foreach ( var ch in right ) { var index = ch - 'a' ; if (++ rightCount [ index ] > leftCount [ index ]) return false ; } return true ; } public int GetHashCode ( string obj ) { var hashCode = 0 ; for ( int i = 0 ; i < obj . Length ; ++ i ) { hashCode ^= 1 << ( obj [ i ] - 'a' ); } return hashCode ; } } public class Solution { public IList < IList < string >> GroupAnagrams ( string [] strs ) { var dict = new Dictionary < string , List < string >>( new Comparer ()); foreach ( var str in strs ) { List < string > list ; if (! dict . TryGetValue ( str , out list )) { list = new List < string >(); dict . Add ( str , list ); } list . Add ( str ); } foreach ( var list in dict . Values ) { list . Sort (); } return new List < IList < string >>( dict . Values ); } } ``` ### CPP ```cpp class Solution { public: vector> groupAnagrams(vector &strs) { unordered_map> d; for (auto &s : strs) { string k = s; sort(k.begin(), k.end()); d[k].emplace_back(s); } vector> ans; for (auto &[_, v] : d) ans.emplace_back(v); return ans; } }; ``` ### Python ```python ''' >>> from collections import defaultdict >>> d = defaultdict(list) >>> d["a"]=1 >>> d["b"]=2 >>> d defaultdict(, {'a': 1, 'b': 2}) >>> d.values() dict_values([1, 2]) >>> list(d.values()) [1, 2] ### sorted(str) will return a list of chars >>> a = "sdfddxyz" >>> sorted(a) ['d', 'd', 'd', 'f', 's', 'x', 'y', 'z'] >>> "".join(sorted(a)) 'dddfsxyz' ''' class Solution : def groupAnagrams ( self , strs : List [ str ]) -> List [ List [ str ]]: d = defaultdict ( list ) for s in strs : k = "" . join ( sorted ( s )) d [ k ]. append ( s ) return list ( d . values ()) ```