49. Group Anagrams — LeetCode(Python)

2 min readJul 15, 2022

I got you!

Problem:

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.

Solution:

res = defaultdict(list)
for s in strs:
            
    count = [0] * 26
    for c in s:
        count[ord(c) - ord('a')] += 1
            
    res[tuple(count)].append(s)
        
return res.values()

Explanation —

This is one of those string questions. This is where we realize the value of hashmaps and arrays.

We are essentially creating a mapping from frequency of each alphabet in a given string to the string itself.

This would mean, strings with same frequency arrays, would be mapped together.

For example,

"ate", "eat" and "tea" will all be mapped to the frequency array:
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
#a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z

where the index of the array represents the alphabet in lexicographic order.

We name our frequency array as counts.

After creating a frequency array for a string, we map it to the string itself. We append the current string to it’s key-value pair.

Finally, we return the values in our res dictionary, because they hold all anagrams together.

Time and Space Complexity —

We are traversing every string only once and while doing so we are iterating over all characters in that string. So we can say that this is a linear time operation.

Also, we are storing all strings in our dictionary, which requires linear space.

The creation of the count array can be overlooked because it always has 26 elements in it, creating and iterating over which takes constant time and requires constant space.

Thus, if m is the length of the list strs, and n is the average length of each string(strings can be of different lengths),

Time Complexity: O(26mn) or O(mn)

Space Complexity: O(m)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏