Write a function to check whether two strings are anagrams of each other. What is the optimal time complexity?
Sorting both strings and comparing is O(n log n). Using Counter or a character frequency array is O(n) and is the preferred approach. The solution must handle case sensitivity and spaces consistently or the comparison will silently give wrong answers.
How to think about it
This is a frequency-counting problem in disguise. Two strings are anagrams if and only if they contain exactly the same characters with exactly the same counts. Once you frame it that way, the solution almost writes itself.
What’s really being tested
The interviewer wants to see whether you think about time complexity and edge cases like case sensitivity and spaces. Jumping straight to sorted(s) == sorted(t) is fine as a first pass, but the follow-up will always be “can you do better than O(n log n)?”
Step 1 — The naive sort approach
Sorting both strings and comparing works because two strings with the same character frequencies will sort to the same string:
def is_anagram_sort(s: str, t: str) -> bool:
return sorted(s) == sorted(t)Simple, but O(n log n). Good enough in many interviews if you name the complexity.
Step 2 — O(n) with Counter
Counter builds a frequency map in one pass. Two Counters are equal if every character has the same count in both — handles length differences automatically because missing keys default to 0.
Step 3 — Early exit with length check
If lengths differ, they can’t be anagrams. This turns a common case into O(1):
Step 4 — Normalise for real-world inputs
“Astronomer” and “Moon starer” are anagrams, but only if you strip spaces and ignore case first.
The key insight — why Counter beats sort
Counter is O(n) time and O(k) space where k is the number of distinct characters (at most 26 for lowercase letters, so effectively O(1) space for fixed alphabets). Sorting creates a new sorted list — O(n log n) time and O(n) extra space.