Instead of sorting the string, this approach creates a unique hash key for each string based on the frequency of characters. This improves performance by avoiding costly sort operations for every string.
Steps
- Initialize a hashmap to store grouped anagrams.
- For each word in the input array:
- Create an array of size 26 to count frequency of each letter.
- Convert that frequency array into a unique string key (like “#1#0#2…”).
- Use this string as a hash key to group anagrams.
- Return all the grouped values.
Dry Run
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
"eat"→ freq =[1,0,0,...,1,1,...]→ key = “#1#0#0#0…#1#1”- All anagrams like “tea” and “ate” will have the same key.
- Final groups:
[["eat","tea","ate"],["tan","nat"],["bat"]]
Time & Space Complexity
- Time Complexity: O(n·k), where n = number of strings, k = average length of strings (no sorting)
- Space Complexity: O(n·k), for storing frequency map and result
var groupAnagrams = function(strs) {
let map = {};
for (let i = 0; i < strs.length; i++) {
let freqArr = Array(26).fill(0);
let s = strs[i];
for (let j = 0; j < s.length; j++) {
let index = s[j].charCodeAt(0) - 'a'.charCodeAt(0);
freqArr[index]++;
}
let key = "";
for (let k = 0; k < 26; k++) {
key += "#" + freqArr[k];
}
if (!map[key]) {
map[key] = [s];
} else {
map[key].push(s);
}
}
return Object.values(map);
};
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for (string s : strs) {
vector<int> freq(26, 0);
for (char c : s) {
freq[c - 'a']++;
}
string key;
for (int count : freq) {
key += "#" + to_string(count);
}
map[key].push_back(s);
}
vector<vector<string>> result;
for (auto it : map) {
result.push_back(it.second);
}
return result;
}
import java.util.*;
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
int[] freq = new int[26];
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
StringBuilder key = new StringBuilder();
for (int count : freq) {
key.append("#").append(count);
}
map.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
}
from collections import defaultdict
def groupAnagrams(strs):
anagram_map = defaultdict(list)
for s in strs:
freq = [0] * 26
for char in s:
freq[ord(char) - ord('a')] += 1
key = tuple(freq)
anagram_map[key].append(s)
return list(anagram_map.values())
