Group Anagrams

Problem:
Given an array of strings strs
, group the anagrams together. You can return the answer in any order.
๐ Example:
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"], ["nat","tan"], ["ate","eat","tea"]]
๐ง Intuition
All anagrams share the same characters in the same frequency, just in a different order.
So how do we know if two words are anagrams?
๐ฏ Trick:
If we sort the letters in both words, and they are equal โ they are anagrams!
"eat"
โ"aet"
"tea"
โ"aet"
โ So,
"eat"
and"tea"
are anagrams!
So let's:
Sort each word.
Use a map (
unordered_map
) to group all words with the same sorted string.
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> anagramMap;
for (string word : strs) {
string sortedWord = word;
sort(sortedWord.begin(), sortedWord.end());
anagramMap[sortedWord].push_back(word);
}
vector<vector<string>> result;
for (auto& matched : anagramMap) {
result.push_back(matched.second);
}
return result;
}
};
Your job is:
Take each word from a list
Sort its letters
Put it into the bucket with that label (sorted letters)
๐ Optimized Solution (No Sorting)
You can improve time from O(N * M log M)
to O(N * M)
(by skipping sorting and using a frequency count as the key).
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> anagramMap;
for (string& word : strs) {
vector<int> count(26, 0);
for (char c : word)
count[c - 'a']++;
// Convert count vector to a unique string
string key;
for (int freq : count) {
key += to_string(freq) + "#"; // '#' as delimiter to avoid ambiguity
}
anagramMap[key].push_back(word);
}
vector<vector<string>> result;
for (auto& entry : anagramMap) {
result.push_back(entry.second);
}
return result;
}
๐ Time & Space Complexity
Method | Time Complexity | Space Complexity |
Sorting-based | O(N * M log M) | O(N * M) |
Char count based โ | O(N * M) | O(N * M) |
N
= number of wordsM
= max length of a word
problem link: https://leetcode.com/problems/group-anagrams/
Subscribe to my newsletter
Read articles from Nikhitha directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by

Nikhitha
Nikhitha
๐ Software Developer | DSA Enthusiast | Problem Solver ๐น Sharing daily DSA solutions, coding insights, and interview prep ๐น Passionate about writing optimized & bug-free code