Anagrams
Scenario
You have an array of 10,000 words. You need to instantly group together all words that are anagrams of each other (like 'eat', 'tea', and 'ate').
Checking every word against every other word takes O(N^2). Can you do this in a single pass?
Why it exists
Problem: Anagrammatic comparison strips away sequential order. Generating all permutations to check for matches scales factorially (O(N!)), which is computationally impossible for long strings.
Naive approach: Generate all permutations of a string and search an array for matches.
Better idea: Standardize the string into a 'canonical signature' (either by sorting its characters or creating a frequency array) and use a Hash Map to bucket matching signatures together.
Mental model
Imagine deconstructing two Lego structures into piles of raw bricks. If the piles contain the exact same quantity of each color and size, they are anagrams. You don't care how they were built, only what they are made of.
Anagram algorithms rely on equivalence classes. If you map every string to a standardized signature, all anagrams will produce the exact same signature. You can use that signature as a Hash Map key, grouping all original strings in a list attached to that key.
Repeated decision: For each word: compute its signature -> use signature as Hash Map key -> append word to the key's list.
Explanation
To solve 'Group Anagrams', we iterate through the list of strings.
Option 1: Sort the string. 'eat', 'tea', and 'ate' all sort to 'aet'. We use 'aet' as a key in a Hash Map, and append the original strings to its value list: `{'aet': ['eat', 'tea', 'ate']}`. This takes O(K log K) per string, where K is string length.
Option 2: Frequency Array. We count the characters into a size-26 integer array. 'eat' becomes an array with 1 at 'a', 1 at 'e', 1 at 't', and zeros elsewhere. We convert this array into an immutable tuple or a string, and use THAT as the Hash Map key. This takes O(K) time per string, completely bypassing the sorting overhead.
At the end of the pass, the values of the Hash Map contain perfect lists of grouped anagrams.
Key points
- Canonical Signatures: Anagram algorithms always transform strings into a uniform representation that ignores original ordering.
- O(N * K) Time Limit: By using a frequency array signature instead of sorting, grouping N strings of maximum length K takes optimal O(N * K) time.
- Hash Map Bucketing: The standardized signature acts as the exact memory address (key) to group related data.
Pattern: Canonical Signature Mapping
Recognition cues:
- The problem asks to 'group' related permutations.
- The problem asks if one string is an anagram of another.
Failure signals
- You are using a library to generate permutations (`itertools.permutations`).
- You are using an O(N^2) nested loop to compare every string with every other string.
Engineering examples
Search Engine Indexing
Returning results for a user's query even if they swapped the order of the letters.
Indexing engines map sorted/standardized versions of words to documents, bypassing typos instantly.
Cryptanalysis
Breaking a transposition cipher.
Transposition ciphers only rearrange letters. The ciphertext and plaintext are perfect anagrams sharing identical frequency signatures.
When not to use
- The character set is massive (full Unicode): Creating a frequency array signature for Unicode is highly inefficient. In this case, the O(K log K) sorting method is actually preferred over a sparse array.
Common mistakes
- Using mutable arrays as Hash Map keys: In Python and Java, arrays/lists cannot be used as dictionary keys because they are mutable (unhashable). You must convert the frequency array to a string or tuple first.
- Assuming lengths are equal: Always check if strings have different lengths immediately. If `len(A) != len(B)`, they mathematically cannot be anagrams. Return false instantly.
Glossary
- immutable tuple
- An unchangeable list of values.
- equivalence classes
- Groups where all items are considered equal based on a specific rule.
- unhashable
- Unable to be used as a dictionary key because its value can change.
Recall questions
- What are the two ways to create a canonical signature for an anagram?
- Why is the frequency array signature faster than the sorting signature?
- Why do we use a Hash Map in grouping anagrams?
Questions & answers
Given an array of strings, group the anagrams together in O(N*K) time.
Iterate through the array. Convert each string into a size-26 frequency tuple. Use the tuple as a Hash Map key, appending the string to the value list. Return all the lists.
Approach: Frequency array signatures with Hash Map bucketing.
Determine if two given strings are valid anagrams of each other.
Check if lengths are equal first. Create a size-26 integer array. Increment for chars in string1, decrement for string2. If the array has any non-zero value at the end, return false. Otherwise, return true.
Approach: Direct addressing frequency array.
Interesting facts
- You can generate a perfect anagram signature using prime numbers: assign each letter a unique prime, and multiply them. The product is guaranteed to be unique (Fundamental Theorem of Arithmetic), but it causes integer overflow rapidly in code.
Continue learning
Previous: Frequency Arrays
Related: Frequency Arrays