Group Anagrams

NikhithaNikhitha
2 min read

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:

  1. Sort each word.

  2. 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

MethodTime ComplexitySpace Complexity
Sorting-basedO(N * M log M)O(N * M)
Char count based โœ…O(N * M)O(N * M)
  • N = number of words

  • M = max length of a word

problem link: https://leetcode.com/problems/group-anagrams/

0
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