Group Anagrams — Editorial

Opening the reading…

Intuitionanagrams become equal when their letters are put in a canonical order

Two strings are anagrams exactly when they contain the same letters with the same frequencies. Their original order is irrelevant, so sorting each string gives every anagram the same key: eat, tea, and ate all become aet. A hash map can then use that key to place matching strings in one bucket while keeping unrelated strings apart.

The buckets are not yet the required answer. Each bucket must be sorted so its strings have a deterministic order, then its members must be joined with commas. Finally, the completed group strings must be sorted lexicographically because hash map iteration order is arbitrary and the output requires a canonical ordering.

Approach

Create a hash map from a canonical key to the original strings that share it, because equal keys are exactly what identifies one anagram group.

For each input string, copy it into key and sort the copy, because sorting the original would destroy the spelling that must appear in the output.

Append the original string to groups[key], so every string with the same sorted letters accumulates in one bucket without comparing it against every existing group.

Iterate through every bucket and sort its strings lexicographically, because the strings inside each returned group must be ordered even though insertion and hash map iteration are not deterministic.

Build one group string by appending each sorted member and placing a comma before every member after the first, because a trailing comma would change the required format.

Append each finished group string to result, then sort result lexicographically, because the hash map does not define the order in which groups are visited.

Return result after all formatting and sorting is complete, because returning the buckets directly would expose keys and would not match the required list of strings.

Complexitysorting work plus the cost of comparing variable-length strings

MEASURE	BOUND	WHY
Time	O(nL log L + nL log n + gM log g)	Each input string is sorted to form its key, costing O(L log L) in the worst case. Sorting all buckets performs at most O(n log n) string comparisons, each inspecting up to L characters. Sorting the g finished group strings performs O(g log g) comparisons, each costing up to M characters.
Space	O(nL) extra, excluding the returned output	The map stores copies of all input strings and their sorted keys, whose total size is O(nL); the temporary keys and group-building buffers do not exceed that order. The returned group strings are required output and are excluded. The bound reaches O(nL) when many long strings are stored in the buckets.

Here n is the number of input strings, L is the maximum input string length, g is the number of groups, and M is the maximum length of one finished group string. Hash map operations are expected O(1) after their keys are built.

Annotated solutionC++ · sorting-based keys · the direct hashing version

CPPSort each string for its hash key, format every bucket, then sort the finished groups.

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

using namespace std;

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

        for (const string& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            groups[key].push_back(s);
        }

        vector<string> result;
        for (auto& entry : groups) {
            vector<string>& members = entry.second;
            sort(members.begin(), members.end());

            string group;
            for (size_t i = 0; i < members.size(); ++i) {
                if (i > 0) {
                    group += ",";
                }
                group += members[i];
            }
            result.push_back(group);
        }

        sort(result.begin(), result.end());
        return result;
    }
};

The copy into key is essential: the sorted form identifies the bucket, while the untouched s is what the answer must print. The two later sorts serve different purposes. Sorting members controls the order inside one comma-separated group; sorting result controls the order among groups. Removing either sort can still pass tests with one group or already ordered input, which makes the omission easy to miss.

The frequency-signature alternativean optimisation that avoids sorting each input string

Because the input uses only lowercase English letters, you can represent a key with 26 character counts instead of sorting the string. This changes key construction from O(L log L) to O(L), while the grouping and output-formatting work remains. It is a genuine optimisation for longer strings, but the sorted key is shorter to explain and less dependent on the alphabet restriction.

CPPUse a 26-count signature instead of sorting each input string.

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

using namespace std;

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

        for (const string& s : strs) {
            vector<int> count(26, 0);
            for (char ch : s) {
                ++count[ch - 'a'];
            }

            string key;
            for (int frequency : count) {
                key += to_string(frequency);
                key += '#';
            }
            groups[key].push_back(s);
        }

        vector<string> result;
        for (auto& entry : groups) {
            vector<string>& members = entry.second;
            sort(members.begin(), members.end());

            string group;
            for (size_t i = 0; i < members.size(); ++i) {
                if (i > 0) {
                    group += ",";
                }
                group += members[i];
            }
            result.push_back(group);
        }

        sort(result.begin(), result.end());
        return result;
    }
};

The separators in the frequency key are deliberate. Without them, adjacent counts could be ambiguous when counts have multiple digits; with a separator after every count, the 26 positions remain unambiguous. This version is not a different output strategy: it is only a faster way to compute the same grouping key, and it still needs both formatting sorts.