Group Anagrams
Understanding the Problem
Two strings are anagrams if they contain exactly the same characters with exactly the same frequencies. "eat" and "tea" are anagrams because both have one 'e', one 'a', and one 't'. Order doesn't matter, only the character composition does.
The question becomes how to create a "fingerprint" for each string such that all anagrams share the same fingerprint and no two non-anagrams collide. Given that, we group strings by their fingerprint using a hash map.
This is a grouping problem, and the challenge is choosing the hash map key.
Key Constraints:
1 <= strs.length <= 10^4→ Up to 10,000 strings. Comparing every string against every other would be O(n^2) string comparisons. Grouping by a hash key avoids that and processes each string once.0 <= strs[i].length <= 100→ Strings are at most 100 characters, so sorting a single string is cheap and building a 26-slot frequency array is constant work. Strings can also be empty, and the empty string is its own valid group.lowercase English letters only→ Only 26 possible characters, so a fixed-size array of 26 counts captures everything a key needs to distinguish.
Approach 1: Sorting
Intuition
If two strings are anagrams, they contain the same characters, so sorting both alphabetically produces the same string. "eat" sorts to "aet", "tea" sorts to "aet", and "ate" sorts to "aet". That sorted form is a canonical fingerprint shared by every anagram and by nothing else: a non-anagram differs in at least one character, so its sorted form differs too.
For each string, sort its characters to produce a key, then use a hash map to group all strings that share the same key.
Algorithm
- Create a hash map where the key is a sorted string and the value is a list of original strings.
- For each string in the input array:
- Sort the characters of the string to produce a key.
- Add the original string to the list associated with that key in the hash map.
- Return all the lists from the hash map as the result.
Example Walkthrough
Code
- Time Complexity: O(n · k log k), where n is the number of strings and k is the maximum string length. We iterate through n strings, and for each string of length k, sorting takes O(k log k). Hashing and inserting the sorted key is O(k). The sort dominates.
- Space Complexity: O(n · k). The hash map stores all n strings, each of length up to k, plus a sorted key of length up to k per string.
Sorting is the bottleneck: every string costs O(k log k) to produce a key. Since the input only contains lowercase English letters, the next approach builds the key from a character count in O(k) time instead of sorting.
Approach 2: Character Frequency Count (Optimal)
Intuition
Since the input only contains lowercase English letters, there are exactly 26 possible characters. Instead of sorting a string into canonical form, count how many times each character appears and use that frequency count as the key.
For "eat": a=1, e=1, t=1. For "tea": a=1, e=1, t=1. Same frequency count, same key.
The frequency array then has to become a hashable key. One way is to join the counts with a delimiter, like #1#0#0#0#1#0#0...#1#0#0..., where each number is the count for a, b, c, ..., z. This produces one string per distinct frequency pattern, avoids sorting, and brings the per-string cost down from O(k log k) to O(k).
Two strings are anagrams if and only if their 26 character counts are identical, so encoding those counts gives a key that anagrams share and non-anagrams never do.
The delimiter between counts matters. Without it, counts like [1, 2, 3] and [12, 3] both produce "123" and collide. A separator such as "#" makes each boundary explicit, so [1, 2, 3] becomes "#1#2#3" and [12, 3] becomes "#12#3".
Algorithm
- Create a hash map where the key is a frequency-encoded string and the value is a list of original strings.
- For each string in the input array:
- Create an array of size 26 (initialized to zeros) to count character frequencies.
- Iterate through the string, incrementing the count for each character.
- Convert the frequency array into a string key (e.g., join counts with a delimiter).
- Add the original string to the list associated with that key in the hash map.
- Return all the lists from the hash map as the result.
Example Walkthrough
Code
- Time Complexity: O(n · k), where n is the number of strings and k is the maximum string length. For each string of length k, counting frequencies is O(k) and building the fixed 26-slot key is O(1). No sorting.
- Space Complexity: O(n · k). The hash map stores all n strings, each up to length k. Each frequency key has a bounded length of 26 counts, so the keys add O(n) overall.
The frequency count approach is optimal in time: you cannot do better than O(n · k), since every character of every string must be read at least once. A different way to build the key uses prime numbers to produce a single number instead of a string. It is instructive, but it has an overflow limitation that the frequency-count approach does not, covered below.
Approach 3: Prime Number Hashing (Alternative)
Intuition
Assign each letter a unique prime number: a=2, b=3, c=5, d=7, e=11, and so on. For each string, multiply the primes for its characters. By the fundamental theorem of arithmetic, every integer has one prime factorization, so two strings produce the same product if and only if they contain the same characters with the same frequencies.
For "eat": 11 · 2 · 71 = 1562. For "tea": 71 · 11 · 2 = 1562, the same product. For "bat": 3 · 2 · 71 = 426, a different product.
This is a numeric key with no string building, no sorting, and no delimiter. The cost is overflow: the product grows multiplicatively, so with the constraint of strings up to 100 characters it exceeds a 64-bit integer (a string of 100 z's would be 101^100). The fixed-width integer versions below wrap around on overflow without any error and can place non-anagrams in the same group, so Approach 2 is the safe default. The JavaScript and TypeScript versions use arbitrary-precision BigInt, so they stay correct at the cost of slower multiplication.
Algorithm
- Define a mapping from each letter (a-z) to a unique prime number.
- Create a hash map where the key is a long integer (the prime product) and the value is a list of original strings.
- For each string in the input array:
- Compute the product of primes for each character.
- Add the original string to the list associated with that product in the hash map.
- Return all the lists from the hash map as the result.
Example Walkthrough
Code
- Time Complexity: O(n · k) with fixed-width integers, since each of the k multiplications is constant time. With arbitrary-precision integers (BigInt), the product grows to O(k) digits, so the multiplications add up to O(k^2) per string and O(n · k^2) overall.
- Space Complexity: O(n · k). The hash map stores all n strings. A fixed-width key is O(1); a BigInt key is O(k) digits, which still adds O(n · k) overall and does not change the asymptotic bound dominated by storing the strings.