vizlearn

Are two strings anagrams?

Interview QuestionsBy Updated

Sorting both and comparing is O(n log n) and fits on one line. Counting is O(n): add up the letters of the first, subtract the letters of the second, and if every count reaches zero they are anagrams. Check lengths first — it is a free rejection.

Overview

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.

StringsCoding problemEasy

Step through it

What to watch

  • The counts rise on the first string and fall on the second.
  • Reaching zero and being deleted is what makes the final check a simple emptiness test.
  • A length mismatch rejects before any counting starts.

Say this out loud

"Sorted comparison is the one-liner, O(n log n). Better is a Counter: add one string, subtract the other, and everything should cancel. O(n) time, O(k) space in the alphabet size."

Are two strings anagrams?

Check whether two strings are anagrams of each other.

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.

Run it in Python

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.

anagram.pyPython 3
Output
How the code works
  1. if len(a) != len(b): return FalseFree, and it removes a whole class of input before any counting. Interviewers notice when it is missing.
  2. del counts[ch]Deleting on zero is what lets the final test be not counts. Leaving zeros in means comparing against a dictionary of zeros instead, which works and reads worse.
  3. if ch not in counts: return FalseCatches a character that is in b and not in a without letting the count go negative. Skipping it gives wrong answers on inputs of equal length.
  4. seen = [0] * 26The fixed-array version, and its assumption. Fast and small for lowercase ASCII, and an IndexError the moment an accent arrives — which the last line demonstrates.
Change one thing
  • Compare Counter(a) == Counter(b) in the timing loop. It is the C implementation of the same idea and wins comfortably.
  • Make the array version case-insensitive with a.lower(). It fixes one assumption and leaves the alphabet one in place.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Counting beats sorting for anagram checks because it is:
  2. Why delete a key when its count reaches zero?
  3. A fixed 26-element array version breaks on:





 Cheat sheet
Are two strings anagrams?
Sorting both and comparing is O(n log n) and fits on one line. Counting is O(n): add up the letters of the first, subtract the letters of the second, and if every count reaches zero they are anagrams. Check lengths first — it is a free rejection.
INTERVIEW · vizlearn.in/interview/valid-anagram.html
More in Interview
InterviewGroup anagrams togetherInterviewLongest substring without repeating charactersInterviewFirst non-repeating characterInterviewValid parentheses
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact