Group Anagrams - Video Solutions

Problem Overview: You receive an array of strings and need to group words that are anagrams of each other. Two strings belong in the same group if they contain the exact same characters with the same frequencies, just arranged in a different order.

Approach 1: Sorted String Key (Hash Table + Sorting) (Time: O(n * k log k), Space: O(n * k))

The most common solution builds a canonical representation for every string by sorting its characters. For each word, convert it to a character array, sort it, and use the sorted string as a key in a hash map. All words that share the same sorted form (for example "aet" for "eat", "tea", and "ate") end up in the same bucket. You iterate through the input once, perform a hash lookup for the sorted key, and append the word to the corresponding list. Sorting each string of length k costs O(k log k), and doing it for n strings results in O(n * k log k) time. This method is straightforward, easy to implement, and widely accepted in interviews.

Approach 2: Character Frequency Signature (Greedy Counting) (Time: O(n * k), Space: O(n * k))

Instead of sorting, build a frequency signature for each string. Create a fixed array of size 26 (for lowercase English letters) and count how many times each character appears. Convert this frequency array into a compact key such as #1#0#0#1... and store it in a hash table. Words that are anagrams produce identical frequency signatures, so they naturally group together. This avoids the sorting step and processes each character exactly once. For n strings with average length k, the algorithm runs in O(n * k) time. The tradeoff is a slightly more complex key construction compared to the sorting approach.

Both strategies rely heavily on fast lookups provided by a hash table and manipulation of string data. The first method uses sorting to normalize each word, while the second replaces sorting with character counting.

Recommended for interviews: The frequency-count hash map solution is usually considered optimal because it reduces the per-string work from O(k log k) to O(k). However, many candidates start with the sorted-key approach because it is easier to reason about and implement quickly. Showing the sorting approach first demonstrates understanding, while moving to the frequency signature highlights optimization skills.