Group Anagrams
Problem statement
You get a list of strings, strs. Group together the strings that are anagrams of each other — strings made of exactly the same letters, just rearranged. Every string belongs to exactly one group, and you can return the groups, and the strings within them, in any order.
Two strings are anagrams if one can be turned into the other by shuffling its letters around, without adding, removing, or changing any letter.
Examples
Example 1
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
Explanation: "ate", "eat", and "tea" all use exactly the letters a, e, t, so they're anagrams of each other. "nat" and "tan" both use a, n, t. "bat" shares no anagram partner in the list, so it's alone in its own group. The grouping shown here is sorted for a consistent, checkable layout — any order of groups, and any order of strings within a group, is equally valid.
Example 2
Input: strs = [""]
Output: [[""]]
Explanation: A single empty string forms a group of one — an empty string is trivially an anagram of itself, and there's nothing else in the list to compare it to.
Example 3
Input: strs = ["a"]
Output: [["a"]]
Explanation: A single one-letter string also forms its own group of one.
Hints
Approach
Optimal: Character count as the group key
Intuition
Sorting is one way to turn a string into a canonical anagram key, but it's not the cheapest way. Since every string here is made only of lowercase English letters, two strings are anagrams exactly when they have the same count of each of the 26 letters. Counting letters is a single O(m) pass, versus sorting's O(m log m) — so build a "count signature" for each string (for example, a tuple or fixed-length string like 1#0#0#...#1#..., one number per letter of the alphabet) and use that as the map key instead of the sorted string.
This is what makes it faster than the Better approach: building the key no longer needs a sort, just one linear scan per string.
Steps
- Create an empty map from a 26-number count signature to a list of original strings.
- For each string
sinstrs, build a length-26 array of zeros, then walk throughsand increment the slot for each letter seen (s[i] - 'a'gives the slot index). - Turn that count array into a hashable key (a tuple in Python, a delimited string in Java/C++), and append
sto the list stored under that key. - Once every string has been processed, return the map's values as the list of groups.
Dry run
strs = ["eat", "tan"]
| string | count signature (a…z, only nonzero shown) | map state after |
|---|---|---|
| eat | a:1, e:1, t:1 | {sig1: ["eat"]} |
| tan | a:1, n:1, t:1 | {sig1: ["eat"], sig2: ["tan"]} |
The two strings get different signatures — "eat" has an 'e' but no 'n', "tan" has an 'n' but no 'e' — so they correctly land in different groups without ever sorting either string.
Edge case: the empty string "" produces a count signature of all zeros, which is distinct from any non-empty string's signature, so every empty string in the input still groups together with other empty strings and nothing else — matching example 2.
Complexity
Time O(n · m) - Each string of length m is scanned once to build a 26-slot letter count, which costs O(m). Doing this for all n strings.
Space O(n · m) - Same as before: every original string ends up stored in some group, and the map additionally holds one small count array temporarily, which isn't kept after its key is built.
class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
groups: dict[tuple, list[str]] = {}
for s in strs:
count = [0] * 26
for ch in s:
count[ord(ch) - ord('a')] += 1
key = tuple(count)
groups.setdefault(key, []).append(s)
return list(groups.values())
if __name__ == "__main__":
print(Solution().groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
print(Solution().groupAnagrams([""]))
print(Solution().groupAnagrams(["a"]))RecapThe whole problem in a few lines, for the night before
- Spot it: "group these strings so that anagrams of each other end up together"
- Idea: give every string a canonical key that's identical for all its anagrams — either its sorted letters, or a count of each letter — and group strings in a hash map by that key
- Cost: sorted-key version is O(n · m log m) time; count-key version is O(n · m) time; both use O(n · m) space
- Trap: comparing every string against every other string directly (or against every existing group) is O(n²)-ish and far too slow — always reduce to a canonical key first, then group with one hash map pass
Interview follow-ups
What if the input is enormous and you want to avoid holding every string in memory to sort or count it?
Process the strings one at a time in a streaming fashion, computing each string's key and appending it directly to an on-disk or external structure keyed by that signature (for example, one file per key), rather than building the full result in memory. The per-string cost stays the same — O(m) for the count-based key — but memory no longer needs to hold every group at once, only whatever buffering the streaming write requires.
How would you group anagrams across multiple case-insensitive languages or alphabets, where the same 26-letter trick doesn't apply?
Replace the fixed 26-slot count array with a hash map from character to count, built the same way — walk the string once, increment the count per character seen. Then use that map's contents (for example, as a sorted list of
(character, count)pairs) as the key. This keeps the same O(m) per-string cost, just without assuming a fixed, known alphabet size.
Frequently asked questions
Sorting a string of length m costs O(m log m) because comparison-based sorting always pays that log factor. Counting each letter's frequency only requires one pass through the string, touching each character exactly once — O(m), with no comparisons or reordering needed. Since the alphabet here is fixed at 26 lowercase letters, a simple fixed-size array is enough to hold the count, so there's no extra cost from a general-purpose data structure either.
The key is meant to be a canonical fingerprint: every anagram of a string must produce identical keys, and no non-anagram may ever produce the same key by coincidence. Both the sorted-string key and the count-signature key have this property — rearranging letters never changes their sorted order or their per-letter counts, and any difference in letters used or how many times they're used produces a different key. If two different keys could collide for non-anagram strings, they'd get wrongly grouped together.
Anagram-of is what's called an equivalence relation — if string A is an anagram of string B, and B is an anagram of C, then A is automatically an anagram of C too. So once a group is confirmed to share one common anagram identity, checking a new string against just that group's first member is enough; there's no need to check it against every member of the group individually.
Grouping items by a derived signature instead of their raw form comes up constantly — clustering config files by their effective content regardless of formatting differences, grouping log lines by a normalized error signature, or deduplicating requests that differ only in argument order. The core trick — reduce each item to a canonical key, then group by that key in a hash map — is the same one used here.
The sorted-string key from the Better approach still works unchanged, since sorting doesn't care what the alphabet is. The count-signature key from the Optimal approach would need a hash map instead of a fixed 26-slot array (since the character set is no longer bounded to 26 known values), which adds a small constant overhead but keeps the same overall O(n · m) time.
