ASAPUtils
The signal
The question is about composition, not order — same characters, same counts, any arrangement. Whenever position is irrelevant and multiplicity is everything, you are looking at frequency counting.
Approach ladder
1. Sort both, compare — O(n log n)
Two lines. Anagrams sort to identical strings. Perfectly correct, and a fine thing to say first.
2. What is sorting wasting?
Sorting produces a total order you never use. You only need to know how many of each character there are — a much weaker fact, and weaker facts are cheaper to compute.
3. Optimal — count, O(n)
Count the characters of s, then decrement while walking t. If any count goes negative, or the
lengths differ, it’s not an anagram. One pass each, no sorting.
The neat single-array version: increment for s, decrement for t, then check every slot is
zero. Even better, check-as-you-go and bail on the first negative.
4. The alphabet decision
If the input is guaranteed lowercase English, use int freq[26] indexed by c - 'a'. It avoids
hashing entirely and the space is genuinely O(1). If the follow-up is “what if the strings are
Unicode?” — and it usually is — swap the array for a hash map and the space becomes O(k) for k
distinct characters. Everything else is unchanged.
Walkthrough
s = "rat", t = "car", single-array version:
| step | char | counts (r, a, t, c) |
|---|---|---|
| count s | r, a, t | r=1, a=1, t=1 |
| walk t | c | c=−1 → negative, return false |
Complexity
- Time O(n) — two linear passes.
- Space O(1) for a fixed 26-letter alphabet; O(k) with a map for arbitrary characters.
Traps
- Forgetting the length check. It’s one line and it short-circuits the whole problem.
- Indexing a 26-slot array with an uppercase or non-letter character. Out-of-bounds in C++, silent nonsense in JavaScript. Read the constraints.
- Comparing maps with
==in JavaScript. TwoMapobjects are never==equal; compare sizes then iterate entries.
Blank re-solve prompt
Given two strings, return whether one is an anagram of the other, in O(n) time without sorting. Then extend it to arbitrary Unicode input.