Group Anagrams

Difficulty: Medium
LeetCode Pattern: Arrays & Hashing

Given an array of strings, group the anagrams together and return them. You can return the answer in any order.

Note: Anagram is a word or phrase formed by rearranging the letters of another word or phrase.

Input:
· ["eat","tan","nat"]
Output:
· [["eat"],["nat","tan"]]

Input:
· ["eat","tan","bat"]
Output:
· [["eat"],["tan"],["bat"]]

• Can input array be empty?

  • Yes, return an empty array.

• Can strings have uppercase letters?

  • No, assume lowercase letters only.

• Can there be empty strings?

  • Yes, put them into the same group.

1/ Sort + Map (Brute Force ⚠️)

• Logic:

  • For each string:

    • Sort it first

    • Then, put it in the map:

      • key = sorted string

      • value = [original string]

• Big O:

  • Time Complexity: O(n·klogk)

  • Space Complexity: O(n·k)

2/ Use Count Arrays (Optimal ✅)

• Idea:

  • Sorting each string takes time

  • But we don’t need to sort

  • We assume strings only contain:

    • 26 unique chars

    • Lowercase letters only

  • So instead of sorting:

    • We use a fixed-size array

    • To keep char counts

• Logic:

  • For each string:

    • Initialize a fixed-size array

    • Keep char counts in it

    • Convert char counts to a key

    • Put it in the map:

      • Key = char counts string

      • Value = [original string]

  • At the end:

    • Return map values (lists) as a list

• Big O:

  • Time Complexity: O(n·k)

  • Space Complexity: O(n·k)

• What if case doesn’t matter?

  • Convert all strings to lowercase.

  • Then run the grouping logic.

• What if input contains Unicode?

  • For Unicode, arrays don’t work.

  • Use a map to count each char.

  • Sort the characters in the map.

  • Turn that into a key string.

  • Group words with the same key.