Print Anagrams Together

Given an array of strings, return all groups of strings that are anagrams. The groups must be created in order of their appearance in the original array. Look at the sample case for clarification.

Note: The final output will be in lexicographic order.

Examples:

Input: arr[] = ["act", "god", "cat", "dog", "tac"]
Output: [["act", "cat", "tac"], ["god", "dog"]]
Explanation: There are 2 groups of anagrams "god", "dog" make group 1. "act", "cat", "tac" make group 2.

Input: arr[] = ["no", "on", "is"]
Output: [["is"], ["no", "on"]]
Explanation: There are 2 groups of anagrams "is" makes group 1. "no", "on" make group 2.

Input: arr[] = ["listen", "silent", "enlist", "abc", "cab", "bac", "rat", "tar", "art"]
Output: [["abc", "cab", "bac"], ["listen", "silent", "enlist"], ["rat", "tar", "art"]]
Explanation: 
Group 1: "abc", "bac", and "cab" are anagrams.
Group 2: "listen", "silent", and "enlist" are anagrams.
Group 3: "rat", "tar", and "art" are anagrams.

Constraints:
1<= arr.size() <=100
1<= arr[i].size() <=10

Approach 01:

class Solution {
  public:
    vector<vector<string>> anagrams(vector<string>& words) {
        unordered_map<string, vector<string>> groupedWords;
        vector<vector<string>> result;
        
        for(const string &word: words){
            string sortedWord = word;
            sort(sortedWord.begin(), sortedWord.end());
            groupedWords[sortedWord].push_back(word);
        }
        
        for(const auto& pair: groupedWords){
            result.push_back(pair.second);
        }
        return result;
    }
};

class Solution:
    def anagrams(self, words):
        groupedWords = {}
        result = []
        
        for word in words:
            sortedWord = ''.join(sorted(word))  # Sort the word alphabetically
            if groupedWords.get(sortedWord) is None:
                groupedWords[sortedWord] = [word]
            else:
                groupedWords[sortedWord].append(word)
        
        # Collect all grouped anagrams
        for _, group in groupedWords.items():
            result.append(group)
        
        return result

Time Complexity:

• Sorting Each Word:
  • For each word in the input list, we sort its characters alphabetically.
  • Sorting a word of length \( k \) takes \( O(k \log k) \).
  • Let \( n \) be the total number of words and \( k \) be the average length of a word. Sorting all words takes \( O(n \cdot k \log k) \).
• Hashing and Grouping:
  • Inserting each word into the hash map (grouping by sorted form) takes \( O(n \cdot k) \), assuming average-case constant-time insertion into the hash map.
• Constructing the Result:
  • Collecting all grouped anagrams from the hash map involves iterating through the hash map entries.
  • This operation takes \( O(n \cdot k) \) to process all words.
• Overall Time Complexity:

  \( O(n \cdot k \log k) \), as sorting dominates the runtime.

Space Complexity:

• Hash Map Storage:
  • The hash map stores each unique sorted word as a key and its corresponding group of anagrams as the value.
  • In the worst case, all words are anagrams, resulting in a hash map of size \( O(n \cdot k) \), where \( k \) is the average word length.
• Auxiliary Space:
  • Sorting each word requires temporary storage for sorting operations, which takes \( O(k) \) space per word.
  • The total auxiliary space for sorting all words is \( O(k) \), reused for each word.
• Result Storage:
  • The final result stores all words grouped into vectors, requiring \( O(n \cdot k) \) space.
• Overall Space Complexity:

  \( O(n \cdot k) \), as the hash map and result storage dominate the space usage.