Given a list of strings strs, group together all strings that are anagrams of each other.

An anagram is a string formed by rearranging the letters of another string, using all original letters exactly once. For example, “eat”, “tea”, and “ate” are anagrams.

Return a list of groups, where each group contains strings that are anagrams of each other.

Note: The order of the groups and the order of strings within each group does not matter.

Constraints:

Let strs be the list of strings given as input to find the anagrams.

• $1 \leq$ strs.length $\leq 10^3$
• $0 \leq$ strs[i].length $\leq 100$
• strs[i] consists of lowercase English letters.

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

The naive approach is to sort all strings first, and then compare them to check whether they are identical. The idea is that if two strings are anagrams, sorting them both will always make them equal to each other. For example, consider the strings “car” and “arc”. When sorted, both these strings become “acr”.

We’ll initialize a hash map to store the anagrams where the key represents the sorted string and the value represents the array of anagrams corresponding to that key. We’ll run a loop on the given list of strings. On each iteration, we will sort the current string. We’ll then check if the sorted string is present as a key in the hash map. If it is, we’ll append the original, unsorted string to the array corresponding to that key. Otherwise, we’ll add the new key-value pair to the hash map. At the end of the traversal, the hash map will contain all the groups of anagrams.

We’ll need $O(n)$ time to traverse the list of strings of length $n$ ...