Run it
Three implementations timed against each other on real words, so the O(n) against O(n log n) claim is measured rather than asserted — and a Unicode case that breaks the fixed-array version.
Two solutions, and the trade between them
Sorting:
One line, O(n log n) time, O(n) space. Correct, and it does more work than the question requires — the order of the sorted characters is irrelevant to the answer.
Counting:
O(n) time, O(k) space where k is the alphabet size. The length check is a cheap early exit and is not strictly necessary, since unequal lengths give unequal counters.
| | Sorting | Counting |
|---|
| Time | O(n log n) | O(n) |
| Space | O(n) | O(k) — bounded by the alphabet |
| One-liner | Yes | Nearly |
| Extends to grouping anagrams | Yes — sorted string as a key | Yes — count tuple as a key |
Mention both. Sorting shows you can produce a correct answer immediately; counting shows you noticed the sort was unnecessary work.
The manual counting version
If asked to avoid library helpers:
One dictionary, two passes, and the second pass decrements rather than building a second count — which is the version worth knowing, because it uses half the space of comparing two dictionaries.
For a known small alphabet, an array of 26 integers replaces the dictionary and is faster:
Single pass over both strings simultaneously, incrementing for one and decrementing for the other. Worth offering as the optimised version when the input is guaranteed lowercase ASCII — and worth noting that it breaks on Unicode, which is exactly the follow-up.
Sorting versus counting
sorted(a) == sorted(b) is correct, obvious and O(n log n). It is a perfectly good answer to give first, and then improve.
Counting is O(n). Build a frequency map of the first string, walk the second decrementing, and check nothing is left over. With a Counter that is two lines; done by hand it is a loop and a dictionary.
Both need the length check first. Different lengths cannot be anagrams, and rejecting there avoids the work entirely.
Space, and the alphabet
The counter holds one entry per distinct character, so space is O(k) in the alphabet rather than O(n) in the input. For lowercase ASCII that is at most 26 entries, which is why interviewers sometimes ask for a fixed 26-element array instead — the same algorithm with the dictionary replaced by an offset from ord('a').
Say out loud that this assumes an alphabet. For arbitrary Unicode the fixed array is wrong and the dictionary is the right structure.
The follow-up that catches people
"Group all the anagrams in a list of words." The instinct is to compare every pair, which is O(n²) comparisons of O(m) strings. The answer is to give every word a canonical key — its sorted letters, or its count tuple — and group by that key in one pass. That is the next question on this track.
Unicode, the interesting complication
The array version assumes 26 lowercase letters. Real text does not.
Accented characters. "café" and "éfac" are anagrams, and ord('é') - 97 is out of range for a 26-element array.
Composed and decomposed forms. "é" can be one code point or an "e" plus a combining accent. Those two strings look identical, contain different characters, and would be reported as non-anagrams. unicodedata.normalize("NFC", s) resolves it, and it should be the first step for any text from the outside world.
Case folding. If case is to be ignored, casefold() is more correct than lower() — it handles cases such as the German ß expanding to "ss".
Raising the normalisation point unprompted is a strong signal in an interview, because it shows awareness that "same characters" is not as simple as it appears.
Edge cases
| Case | Answer |
|---|
| Both empty | Yes |
| Different lengths | No — check first, it is O(1) |
| Same string | Yes — a string is an anagram of itself |
| Spaces and punctuation | Depends on the definition; ask |
| Case differences | Depends; ask |
| Very long strings | Counting is O(n) and preferable |
| Non-ASCII | Normalise first, and use a dictionary rather than a fixed array |
The follow-ups
"Group all anagrams together." The standard escalation. Use the sorted string, or a tuple of counts, as a dictionary key:
O(n × m log m) for n words of length m. A count tuple as the key gives O(n × m) at the cost of a fixed-size key.
"Find all anagrams of a pattern inside a longer string." A sliding window of the pattern's length with a running character count, updated incrementally as the window moves — O(n) rather than re-counting each window.
"What if you cannot use extra space?" Sorting in place, if the strings are mutable. In Python they are not, so this is a question about other languages.
"How would you check a million pairs?" Precompute a canonical form — the sorted string or a count signature — once per string, and compare those. That turns each comparison into a hash lookup.
What it is testing
Do you notice that sorting is more work than needed? Both answers are correct, and recognising the O(n) alternative is the point.
Do you ask about the definition? Case, whitespace and punctuation all change the answer, and asking is expected rather than pedantic.
Do you check lengths first? A one-line early exit that is free.
Do you see the grouping follow-up coming? Using a canonical form as a dictionary key is the transferable idea, and it appears in deduplication, caching and indexing far beyond this problem.
Recap in one screen
- Anagram means identical character counts, so compare counts — O(n) — rather than sorting at O(n log n).
Counter(s) == Counter(t) is the practical answer; a 26-element array is the optimised ASCII version.- Ask about case, whitespace and punctuation before coding.
- Normalise Unicode before comparing, or visually identical strings compare as different.
- The canonical-form-as-dictionary-key idea is what generalises, and grouping anagrams is the standard follow-up.