Group Anagrams medium

Problem Statement

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]

Output: [[""]]

Steps to Solve

1. Create a HashMap: We'll use an unordered map (hashmap) to store the anagrams. The key will be a sorted string representation of each word (since anagrams have the same letters, just rearranged). The value will be a vector of strings, storing all the anagrams with that sorted key.

2. Iterate and Sort: Iterate through the input array strs. For each string:

   • Sort the string alphabetically.
   • Use the sorted string as the key in the hashmap.
   • If the key doesn't exist, create a new vector of strings in the hashmap with that key.
   • Add the original (unsorted) string to the vector associated with that key.

3. Collect Results: After processing all strings, iterate through the hashmap and collect all the vectors of strings (which are the groups of anagrams) into the result vector.

Explanation

The core idea is to use the sorted representation of each string as a unique identifier for its anagram group. Since anagrams have the same letters, sorting them will produce the same sorted string. The hashmap efficiently handles the grouping based on this sorted key.

Code (C++)

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

using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> anagramGroups;
    vector<vector<string>> result;

    for (string& str : strs) {
        string sortedStr = str;
        sort(sortedStr.begin(), sortedStr.end()); // Sort the string
        anagramGroups[sortedStr].push_back(str); // Add to the group
    }

    for (auto const& [key, val] : anagramGroups) {
        result.push_back(val); // Collect the groups
    }

    return result;
}

int main() {
    vector<string> strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> result1 = groupAnagrams(strs1);

    // Print the result (for demonstration)
    for (const auto& group : result1) {
        cout << "[";
        for (size_t i = 0; i < group.size(); ++i) {
            cout << "\"" << group[i] << "\"";
            if (i < group.size() - 1) {
                cout << ",";
            }
        }
        cout << "]" << endl;
    }

    vector<string> strs2 = {""};
    vector<vector<string>> result2 = groupAnagrams(strs2);
    for (const auto& group : result2) {
        cout << "[";
        for (size_t i = 0; i < group.size(); ++i) {
            cout << "\"" << group[i] << "\"";
            if (i < group.size() - 1) {
                cout << ",";
            }
        }
        cout << "]" << endl;
    }


    return 0;
}

Complexity Analysis

• Time Complexity: O(M * N * log N), where N is the average length of strings and M is the number of strings. This is dominated by the sorting step (N log N) done for each string (M strings).
• Space Complexity: O(M * N) in the worst case, where we have to store all strings in the hashmap. In the best case where all strings are unique, space complexity would be O(M).