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:

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

• N = number of words

• M = max length of a word

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