DSA

Group Anagrams

Covers: Sorting + Hashing, character counts Based key. Optimal — Time O(n * k), Space O(n * k).

August 8, 2026
PatternFrequency Count (Hash Map)OptimalO(n * k) time · O(n * k) space
Solve on LeetCode
Key insighttry it first, then reveal

Instead of sorting each string (which costs O(k log k) per string), count the frequency of each of the 26 letters and encode those counts as a string key separated by # delimiters.

Practice Link Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Sorting + Hashing#

  • Sorting each string to use as a key in a hash map.
  • Grouping original strings into a map where the sorted version is the key.
  • Returning the grouped anagrams.
cpp
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for(string s: strs)
        {
            string temp = s;
            sort(temp.begin(), temp.end());

            hash[temp].push_back(s);
        }

        vector<vector<string>> result;
        for(auto &it: hash)
        {
            result.push_back(it.second);
        }
        return result;
    }
};

Time Complexity: O(n * klogk), n = number of strings in strs, k = maximum length of a string

Space Complexity: O(n * k),

character counts Based key#

Instead of sorting each string (which costs O(k log k) per string), count the frequency of each of the 26 letters and encode those counts as a string key separated by # delimiters. Any two anagrams produce identical character-count vectors and therefore identical keys, so they hash to the same bucket. This reduces the per-string cost from O(k log k) to O(k), making the overall algorithm O(n × k) rather than O(n × k log k).

cpp
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for(string s: strs)
        {
            vector<int> count(26, 0);
            for (char c : s)
                count[c - 'a']++;

            // Create a unique key from character counts
            string key="";
            for (int i = 0; i < 26; ++i) {
                key += "#" + to_string(count[i]); // '#' to separate digits properly
            }

            cout<<"string: "<<s<<" key: "<<key<<endl;

            hash[key].push_back(s);
        }

        vector<vector<string>> result;
        for(auto &it: hash)
        {
            result.push_back(it.second);
        }
        return result;
    }
};

Time Complexity: O(n * k), n = number of strings in strs, k = maximum length of a string

Space Complexity: O(n * k),