Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order. For example:

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

• There is no string in strs that can be rearranged to form "bat".
• The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
• The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

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

## Group Anagrams

This problem asks us to group an array of strings into sub-arrays, where each sub-array contains strings that are anagrams of each other. Anagrams are words that contain the same characters, but in a different order.

### Naive Solution

The most straightforward approach is to iterate through each string in the input array and compare it with every other string. For each string, we can check if it's an anagram of any of the other strings.  This would involve sorting each string and comparing the sorted versions.  If two strings have the same sorted version, they are anagrams.

**Code:**

```python
def group_anagrams_naive(strs):
    anagram_groups = []
    used = [False] * len(strs)

    for i in range(len(strs)):
        if used[i]:
            continue

        group = [strs[i]]
        used[i] = True

        for j in range(i + 1, len(strs)):
            if used[j]:
                continue

            if sorted(strs[i]) == sorted(strs[j]):
                group.append(strs[j])
                used[j] = True

        anagram_groups.append(group)

    return anagram_groups

Optimal Solution

The optimal solution uses a hash map to store the sorted version of each string as the key, and a list of anagrams as the value. This allows us to group anagrams in a single pass through the input array.

Algorithm:

1. Create a hash map to store the sorted string as the key and the list of anagrams as the value.
2. Iterate through each string in the input array.
3. Sort the string.
4. If the sorted string is already in the hash map, append the string to the list of anagrams.
5. Otherwise, add the sorted string to the hash map with a new list containing the string.
6. Return the values of the hash map.

Code:

def group_anagrams(strs):
    anagram_map = {}
    for s in strs:
        sorted_s = ''.join(sorted(s))
        if sorted_s in anagram_map:
            anagram_map[sorted_s].append(s)
        else:
            anagram_map[sorted_s] = [s]
    return list(anagram_map.values())

Example

strs = ["eat","tea","tan","ate","nat","bat"]
result = group_anagrams(strs)
print(result)  # Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Big(O) Run-time Analysis

• Naive Solution: O(n²k log k), where n is the number of strings and k is the average length of the strings. This is because we are iterating through each string and comparing it with every other string. For each comparison, we are sorting the strings, which takes O(k log k) time.
• Optimal Solution: O(nk log k), where n is the number of strings and k is the average length of the strings. This is because we are iterating through each string once and sorting it, which takes O(k log k) time. Hash map operations take O(1) on average.

Big(O) Space Usage Analysis

• Naive Solution: O(n), where n is the number of strings. This is because we are using a boolean array to keep track of which strings have been used.
• Optimal Solution: O(nk), where n is the number of strings and k is the average length of the strings. This is because we are storing all of the strings in a hash map.

Edge Cases

• Empty Input Array: If the input array is empty, the function should return an empty list.
• Empty Strings: If the input array contains empty strings, they should be grouped together.
• Strings with Non-alphabetic Characters: If the input array contains strings with non-alphabetic characters, the function should still work correctly.
• Duplicate Strings: If the input array contains duplicate strings, they should be grouped correctly.

Code to handle empty input:

def group_anagrams(strs):
    if not strs:
        return []
    anagram_map = {}
    for s in strs:
        sorted_s = ''.join(sorted(s))
        if sorted_s in anagram_map:
            anagram_map[sorted_s].append(s)
        else:
            anagram_map[sorted_s] = [s]
    return list(anagram_map.values())