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

using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> mp;

        // Iterate over each string in the input vector
        for(auto str : strs) {
            string s = str;
            // Sort the string to use as a key
            sort(s.begin(), s.end());
            // Group the original string under the sorted key
            mp[s].push_back(str);
        }

        vector<vector<string>> ans;

        // Iterate over the map to collect the grouped anagrams
        for(auto it = mp.begin(); it != mp.end(); it++) {
            ans.push_back(it->second);
        }

        return ans;
    }
};

code Breakdown :

  map<string, vector<string>> mp;

        // Iterate over each string in the input vector
        for(auto str : strs) {
            string s = str;
            // Sort the string to use as a key
            sort(s.begin(), s.end());
            // Group the original string under the sorted key
            mp[s].push_back(str);
   }

The purpose of this code is to group anagrams together. Anagrams are words that contain the same characters but in different orders (e.g., "eat", "tea", and "ate" are anagrams).

NEXT :

vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); it++) {
    ans.push_back(it->second);
}

• Data Structures:

  • mp: This is a map<string, vector<string>>. It stores sorted strings as keys and vectors of original strings (anagrams) as values.
  • ans: This is a vector<vector<string>> which will store the grouped anagrams.

• Map Iteration:

  • auto it = mp.begin(): Initializes an iterator it to the beginning of the map mp.
  • it != mp.end(): The loop continues as long as it is not equal to the end iterator of the map.
  • it++: Advances the iterator to the next element in the map.

• Loop Body:

  • it->second: For each element in the map, it->second accesses the value part of the key-value pair in the map, which is a vector<string> (a group of anagrams).
  • ans.push_back(it->second): Adds this vector of strings to the ans vector.

Example Data

Suppose we have the following input:

vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

After processing these strings to group anagrams, the map mp might look like this:

mp = {
    "aet": ["eat", "tea", "ate"],
    "ant": ["tan", "nat"],
    "abt": ["bat"]
}

Iterating Over the Map

• Initialization: auto it = mp.begin()

  • it points to the first element of mp (i.e., "aet": ["eat", "tea", "ate"]).

• First Iteration:

  • it->second is ["eat", "tea", "ate"].
  • ans.push_back(it->second) adds ["eat", "tea", "ate"] to ans.

• Second Iteration:

  • it is incremented (it++) and now points to "ant": ["tan", "nat"].
  • it->second is ["tan", "nat"].
  • ans.push_back(it->second) adds ["tan", "nat"] to ans.

• Third Iteration:

  • it is incremented again and now points to "abt": ["bat"].
  • it->second is ["bat"].
  • ans.push_back(it->second) adds ["bat"] to ans.

• End of Loop:

  • it is incremented one more time and now equals mp.end(), terminating the loop.

FINAL OUTPUT :

ans = {
    {"eat", "tea", "ate"},
    {"tan", "nat"},
    {"bat"}
};

But ...But... There is anathor way ! to Solve this Problem ! using HASHMAPS

class Solution {
public:
    // Function to compute the character frequency hash for a string
    array<int, 256> hash(string s) {
        // Initialize an array of size 256 to store the frequency of each character
        array<int, 256> hash = {0};
        
        // Iterate over each character in the string
        for (int i = 0; i < s.size(); i++) {
            // Increment the count for the current character in the hash array
            hash[s[i]]++;
        }
        
        // Return the character frequency array
        return hash;
    }

    // Function to group anagrams
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // Map to store vectors of strings with the same character frequency array
        map<array<int, 256>, vector<string>> mp;

        // Iterate over each string in the input vector
        for (auto str : strs) {
            // Compute the character frequency array for the current string
            // Use the character frequency array as the key in the map
            // Append the original string to the vector associated with this key
            mp[hash(str)].push_back(str);
        }

        // Vector to store the final groups of anagrams
        vector<vector<string>> ans;
        
        // Iterate over the map to collect the grouped anagrams
        for (auto it = mp.begin(); it != mp.end(); it++) {
            // Append each vector of anagrams to the final result
            ans.push_back(it->second);
        }

        // Return the final result containing groups of anagrams
        return ans;
    }
};

Try to Understand the code ! 

1. Character Frequency Hash Function:

   • array<int, 256> hash(string s):
     • This function computes a character frequency array for a given string s.
     • array<int, 256> hash = {0}; initializes an array of size 256 (to cover all possible ASCII characters) with zeros.
     • for (int i = 0; i < s.size(); i++) { hash[s[i]]++; } iterates over each character in the string and increments the corresponding position in the array to count the character's frequency.
     • return hash; returns the character frequency array.

2. Group Anagrams Function:

   • vector<vector<string>> groupAnagrams(vector<string>& strs):
     • This function groups anagrams from the input vector strs.
     • map<array<int, 256>, vector<string>> mp; defines a map where the key is an array representing character frequencies, and the value is a vector of strings that are anagrams.

3. Populating the Map:

   • for (auto str : strs) { mp[hash(str)].push_back(str); }:
     • Iterates over each string in the input vector strs.
     • Computes the character frequency array for the current string using the hash function.
     • Uses this array as the key in the map mp and appends the original string to the vector associated with this key.

4. Collecting the Results:

   • vector<vector<string>> ans; initializes a vector to store the final groups of anagrams.
   • for (auto it = mp.begin(); it != mp.end(); it++) { ans.push_back(it->second); }:
     • Iterates over the map mp.
     • Appends each vector of anagrams (it->second) to the final result vector ans.

5. Return the Result:

   • return ans; returns the final result containing groups of anagrams.

vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

1. First Iteration (str = "eat"):

   • hash("eat") produces a character frequency array where:
     • hash['e'] = 1
     • hash['a'] = 1
     • hash['t'] = 1
   • Insert "eat" into mp with this array as the key.

2. Second Iteration (str = "tea"):

   • hash("tea") produces the same character frequency array as "eat".
   • Insert "tea" into mp under the same key.

3. Third Iteration (str = "tan"):

   • hash("tan") produces a different character frequency array.
   • Insert "tan" into mp with its own key.

4. Subsequent Iterations:

   • Similarly, "ate" will group with "eat" and "tea".
   • "nat" will group with "tan".
   • "bat" will have its own group.

Final State of the Map

After processing all strings, mp will look like this (conceptually):

mp = {
    {hash("aet")}: ["eat", "tea", "ate"],
    {hash("ant")}: ["tan", "nat"],
    {hash("abt")}: ["bat"]
}

ans = {
    {"eat", "tea", "ate"},
    {"tan", "nat"},
    {"bat"}
}