49. Group Anagrams

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: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Approach 01:

#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <map>

using namespace std;

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

        for (const string& str : strs) {
            string sorted_str = str;
            sort(sorted_str.begin(), sorted_str.end());
            groups[sorted_str].push_back(str);
        }

        vector<vector<string>> result;
        for (const auto& pair : groups) {
            result.push_back(pair.second);
        }

        return result;
    }
};

from typing import *
from collections import *

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)

        for s in strs:
            sorted_str = ''.join(sorted(s))
            groups[sorted_str].append(s)  # sorted_str working as key

        return list(groups.values())

Time Complexity

• Sorting Each String: \( O(m \log m) \)
• Iterating Through All Strings:
  • Sorting each string: \( O(m \log m) \) per string
  • Inserting into unordered map: \( O(1) \) on average
• Overall Time Complexity: \( O(n \cdot m \log m) \)

Space Complexity

• unordered_map `groups`: \( O(n \cdot m) \)
• Vectors in `groups`: \( O(m) \) per string
• Overall Space Complexity: \( O(n \cdot m) \)

Approach 02:

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();
        vector<vector<int>> result(n, vector<int>(26, 0));
        vector<bool> visited(n, false);
        vector<vector<string>> final_result;

        // Calculate frequency arrays for each string
        for (int i = 0; i < n; ++i) {
            for (char ch : strs[i]) {
                result[i][ch - 'a']++;
            }
        }

        // Group anagrams
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                vector<string> temp_list;
                for (int j = i; j < n; ++j) {
                    if (result[i] == result[j] && !visited[j]) {
                        temp_list.push_back(strs[j]);
                        visited[j] = true;
                    }
                }
                final_result.push_back(temp_list);
            }
        }

        return final_result;
    }
};

from typing import *

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        n = len(strs)
        result = []
        final_result = []

        for i in range(n):
            num = [0]*26
            for ch in strs[i]:
                num[ord(ch) - ord('a')] += 1
            result.append(num)

        visited = []
        for i in range(n):
            temp = result[i]
            temp_list = []
            for j in range(i,n):
                if(temp == result[j] and (j not in visited)):
                    temp_list.append(strs[j])
                    visited.append(j)
            if(len(temp_list)!= 0):
                final_result.append(temp_list) 

        return final_result

Time Complexity

Calculating Frequency Arrays:
\( O(n \cdot m) \), where \( n \) is the number of strings (\( \text{strs} \)) and \( m \) is the average length of strings.

Grouping Anagrams:
\( O(n^2 \cdot m) \), where \( n \) is the number of strings (\( \text{strs} \)) and \( m \) is the average length of strings.

Overall Time Complexity:
\( O(n^2 \cdot m) \), where \( n \) is the number of strings (\( \text{strs} \)) and \( m \) is the average length of strings.

Space Complexity

Frequency Arrays (\( \text{result} \)):
\( O(n \cdot m) \), where \( n \) is the number of strings (\( \text{strs} \)) and \( m \) is the size of the frequency array (constant 26 for each string).

Visited Array (\( \text{visited} \)):
\( O(n) \), where \( n \) is the number of strings (\( \text{strs} \)).

Final Result (\( \text{final_result} \)):
\( O(n \cdot m) \), in the worst case when no strings are grouped together.

Overall Space Complexity:
\( O(n \cdot m) \), where \( n \) is the number of strings (\( \text{strs} \)) and \( m \) is the average length of strings.