Group Anagrams - Categorize Strings by Count - Leetcode 49

Dang, I almost got it myself but exceeded the time limit 🥲

What if we do not know about of what letters are our words. We can then use HashMaps for counting and as our keys, right?

O(m logn)
from collections import defaultdict, Counter
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list)
for i in strs:
res[tuple(sorted(Counter(i).items()))].append(i)
return res.values()

There's no need to subtract the ascii value of each character from A's ascii value. Just use the characters ascii directly as the key in the hashmap, so change count = [0] * 256.

I feel like this problem is easy to work out in your head than to actually implement... bruh
but after watching this video, the implementation is easier than it initially had it

In c++ ,you can use an integer as keys. And use bits operation to represent the words contains what alphabet. No matter what sequence the alphabet comes in.

Great video!! just wondering, I see the point of the time complexity mn. However I keep wondering you will need a word of over 10^26 characters for mnlogn to become less efficient than (mn26)->mn. 10^26 is pretty much infinity already, I mean only for strings over 10^26 characters it would be better to do it this way. for instance, if n =10, nlogn =10 and n26=260, if n=10,000,000 nlogn = 70,000,000 and n26=260,000,000. I'm probably misunderstanding, could you please share some insight on this? Thank you!

Well, sorting the words and storing them as keys in the dict and the anagram in the values gave me better results both in runtime and memory. I'm not good with BigO yet, so I'm not sure what it is for mine solution:
Im a newbie with python too, so maybe there is a cleaner or shorter way to write what I did:
result = {}
for i, item in enumerate(strs):
anagram = ''.join(sorted(item))
if anagram in result:
anagram_list = result[anagram]
anagram_list.append(item)
result[anagram] = anagram_list
else:
data = []
data.append(item)
result[anagram] = data

resp = []
for item in result:
resp.append(result[item])

return resp

Thank you! Never would have thought of making the keys the ASCII character count, that is pretty clever

I was able to come up with a solution before looking it up :)
not optimal but I was glad I was able to solve it. Thanks in part to your videos.

def groupAnag(list):
result = {}
for item in list:
itemResult = []
for letter in item:
itemResult.append(letter)
itemResult.sort()
itemResult = ''.join(itemResult)
if itemResult in result:
result[itemResult].append(item)
else:
result[itemResult] = [item]
my_list = [i for i in result.values()]
return my_list

Maybe we can get rid of mapping strings with integer list and use sorted keys.
Something like below worked for me:

ans = defaultdict(list)
for str in strs:
sorted_str = sorted(str)
ans[tuple(sorted_str)].append(str)

return ans.values()

Set up a dictionary and output list.

Iterate thru the input strings.
For each input string, create a separate sorted string.

If the sorted string is a key in the dictionary,
append the input string to a list in the key's value

If the sorted string is not a key in the dictionary,
set up a new key value pair where the key is the sorted string,
and the value is a list holding just the input string.

Iterate thru the values of the the dictionary,
append them to the output list.

Return this output list.

If you don't want to use defaultdict() from collections, you may do this:

def groupAnagrams(strs):
res = {}
for s in strs:
count = [0] * 26 # a .... z
for c in s:
count[ord(c) - ord("a")] += 1
key = tuple(count)
if key in res:
res[key].append(s)
else:
res[key] = [s]

return list(res.values())

Why is the sorted version run at a lower runtime on leetcode eventhough this solution is better in theory. Leetcode runtimes are pretty weird.

why we are use '#' there and what is its importance ?

Amazing... How come you can get to these ideas. It is simple, but it is hard to get to these solutions without hints :)

JAVA code
I really should learn python:
28 lines vs 8 lines
public static List<List<String>> groupAnagrams(String[] strs) {
Map<List<Integer>, List<String>> hm = new HashMap();

for(String s: strs) {
int count[] = new int[26];
for(Character c: s.toCharArray()) {
count[c-97]++;
}
List<Integer> alphabet_count = new ArrayList<Integer>();
for(int i: count){
alphabet_count.add(i);
}
if(!hm.containsKey(alphabet_count)){
List<String> result_map_value = new ArrayList<String>();
result_map_value.add(s);
hm.put(alphabet_count, result_map_value);
}
else {
List<String> result_map = hm.get(alphabet_count);
result_map.add(s);
hm.put(alphabet_count, result_map);
}
}
List<List<String>> final_result_list = new ArrayList<List<String>>();
for (Map.Entry<List<Integer>, List<String>> entry : hm.entrySet()) {
final_result_list.add(entry.getValue());
}
return final_result_list;
}

var groupAnagrams = function (strs) {
const anagramsMap = new Map();

for (let str of strs) {
const charsCount = new Array(26).fill(0);

for (let char of str) {
charsCount[char.charCodeAt(0) - 97]++; // "a".charCodeAt(0) = 97 in the Unicode
}

const hash = charsCount.toString();

anagramsMap.set(hash, (anagramsMap.get(hash) || []).concat(str)); // much shorter than if statements
}

return Array.from(anagramsMap.values());
};

I have a question for the M * n* log(n) solutions. I also came up with that, but one has to return the unsorted strings. So I am assuming that you also made a deep copy of strs to not fiddle with the order of characters?

I didn't pay attention to the 26 characters part at first. And my python code ran out of execution time on leetcode 😢

My solution in typescript:
function groupAnagrams(strs: string[]): string[][] {
const sortedMap = new Map();
for (let i = 0; i < strs.length; i++) {
// Sort each item
const key = strs[i].split("").sort().join("");
// Add items as keys in the map. If one exists already concat it so it is in the right form [..., ...]
sortedMap.set(key, (sortedMap.get(key) || []).concat(strs[i]));
}
return Array.from(sortedMap.values());
};

aswome

I've found an even faster solution that doesn't require ascii math:

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dict = defaultdict(list)
for str in strs:
sortedstr = ''.join(sorted(str))
if sortedstr in dict:
dict[sortedstr].append(str)
else:
dict[sortedstr] = [str]
return dict.values()

it's quite similar but essentially it sorts each str in strs. Then, if sortedstr is in dict, append to dict[sortedstr], otherwise append [str] to dict. return dict.values()

hope this helps someone

I went with a different approach where I just check whether sorted(string) is in the dict, if not then just store an array against that sorted string in the dict

How does this work because I thought you cannot key a dictionary with a list in python?

If you're like me and doing this cause you couldn't figure it out on your own, I usually take notes on my code in the comments so I understand the logic when I come back to it and to solidify it in my head.

hope this helps!

Thank you @NeetCode for all the great videos! I just want to point out that the optimal approach is great for a large n but in case of this particular problem because n is limited to max of 100 (0 <= strs[i].length <= 100), log(n) would be 6.6 which makes m*n*log n faster than m*n*26

My brain is fuming, I'm not made for developping...

I originally tried to solve this by creating a hash using the char codes of each char in a string and using the hash as the key to group the values. I had a ton of collisions as my hashing function was crappy. Was wondering if you'd revisit this and solve with hashing?

No way, the code is this concise and clear in Python. That's it. I am divorcing Java for leetcode. Switching to python.

understood

i dunno if anyone will see this but is accessing the hash map with keys of an array really constant time and gonna work lol?

I'm confused. What about for a test case like ["ab","c"]. ab and c both = 3 so they would just go in same list even though they are not anagrams?

First of all, thanks for your work.

I coded first and second solutions in python3, solution 1 (using sorted strings) seems to perform better in speed use and in memory use on leetcode test cases.

would it be better to use a hashmap to count the letters and use that as the key instead of reusing an array with 26 spots for each letter in the alphabet? I feel like that is wasting a lot of memory and using a hashmap would slightly improve on that

Oh my god I feel so stupid. Every leetcode question I am mind boggled and I come here for answers after hours of trying JUST FOR THE ANSWERS TO BE VERY SIMPLE. MY INTERVIEW IS TODAY AND I WILL NOT MAKE IT. I will never be a good programmer. Like every question I do I never think of the correct answer even if its very basic. I feel like im wasting my time. Im so scared that I wont make it as a successful programmer no matter how hard I try. This question was the last straw for me and im losing my mind rn.

How the length of the count array is 26??

Does anyone know the space complexity?

Nice explanation @NeetCode. Mind me but I have something to discuss, I'm not a master at this, just a thought I'm having. Considering we have 100 characters in a substring n, it will take us 100 characters to check the character and save it in the hash instead of just 26, wouldn't it be better to sort it with "log-n". I believe this might make the worst memory usage, since instead of counting, this time we will be saving the whole string.

yeah I would've never thought of the ASCII value stuff. Twas thinking about going with Counter and using the result as a key if possible

nah its not worth it, O(m*nlogn) might perform better

I wonder how storing array as a key will work in C# or java, since even if 2 array sequence are same, dictionary.ContainsKey(array) will be always false since we are doing new int[25] on each iteration.

Wouldn't this algorithm fail if encountered two words with same sum but different characters ? such as "eat" & "bas" I know "bas" isn't a word but still they would match.

You automatically assumed that sorting the alphabets of each string is O(nlog(n)). This only applies for a comparison based sort. However, you can sort using counting sort which will end up taking O(26) + O(n) time (or O(n)) plus O(n) additional space. If we serialize the output of counting sort as character followed by count, instead of constructing the whole sorted string, we will end up with exactly the same key as you got. A hashmap can then be used as usual to finish the problem.

The downside of this approach is that you're using a hashmap. What's bad here is that we don't know how the hash of the key is calculated and we don't consider if there're hash collisions and therefore we can't guarantee that our operations with hashmap will be O(1). Because the hashmap is used inside a for loop, the overall complexity will be O(m*n^2)

what a smart solution