I failed this problem in a 25-minute phone screen at a mid-size fintech, and it is rated Easy.
Not Medium. Not Hard. Easy. I had done 140 problems by then, mostly by reading solutions and nodding along, and when the shared editor opened and the prompt said "Valid Anagram," I wrote a nested loop, watched it not work, deleted it, wrote a sorting one-liner, and then could not answer "can you do better than O(n log n)?" because I had never actually been taught the thing the problem was testing. So this is valid anagram explained for beginners — the slow version, the one I needed at 11pm on a Tuesday with a rejection email already in my inbox.
This problem shows up at 20+ companies. Goldman Sachs, Indeed, ServiceNow, Etsy. It is high frequency precisely because it is a five-minute filter: the interviewer is not checking whether you can solve it. They are checking whether you already know the counting pattern, because if you do, a dozen harder problems get easier. Nobody sends you a memo about that. You are expected to have absorbed it from a friend who did the same internship you didn't get.
What "anagram" actually means here
Start with plain English. You get two strings. Call them s and t. You return true if t is a rearrangement of s, using every letter of s exactly as many times as s uses it, and false otherwise.
The example I am going to carry through this entire piece:
s = "anagram"t = "nagaram"
Same seven letters, shuffled. Answer: true.
And the counterexample:
s = "rat"t = "car"
Answer: false. Both are three letters, both contain r and a, but s has a t and t has a c.
Now the trap, and it is a real one because the word "anagram" comes from crossword puzzles, not from computer science. Three wrong ideas the word plants in your head:
It does not have to be a real word. "aab" and "aba" are anagrams for our purposes. No dictionary is involved.
It does not have to be a different arrangement. "abc" and "abc" return true. The problem asks whether the letters match, not whether anything moved.
And this is the one that quietly kills people: the letters matter, but so do the quantities. Consider s = "aab" and t = "abb". Same distinct letters — a and b appear in both. If you check "does every letter in s appear somewhere in t," you get true, and you are wrong. s has two as and one b. t has one a and two bs. The answer is false.
Write that down somewhere: this problem is about counts, not about membership. Everything below is a consequence of that sentence.
Sorting works — but what does it cost?
Here is the first thing most people write, and I mean it kindly, because I wrote it too. For each character in s, go look for it in t and cross it out so it can't be matched twice:
def isAnagram_bruteforce(s, t):
if len(s) != len(t):
return False
remaining = list(t) # mutable copy of t
for ch in s:
if ch in remaining: # scan the whole list
remaining.remove(ch) # scan it again to delete
else:
return False
return True
This is correct. It also scans remaining from the front for every single character of s. If s has n characters and remaining has up to n characters, you are doing roughly n × n units of work. That is O(n²).
Concrete numbers, because "O(n²) is slow" means nothing until you feel it. Say the strings are 50,000 characters — well within what a judge will throw at you. n² is 2,500,000,000. Two and a half billion character comparisons. On a typical judge that is somewhere north of a minute, against a limit of one or two seconds. Time Limit Exceeded, and you never find out whether your logic was right.
The second thing most people write is the sorting trick:
def isAnagram_sorted(s, t):
return sorted(s) == sorted(t)
Sort both strings alphabetically. "anagram" becomes aaagmnr. "nagaram" becomes aaagmnr. Identical, so true. This is genuinely correct and genuinely fine — it will pass. It costs O(n log n) time, because that is what comparison sorting costs, plus O(n) space for the two sorted copies.
For n = 50,000, n log n is about 780,000 operations. Three thousand times better than the brute force. Fast enough.
But here is the question that ended my phone screen: can you do it in linear time? And the honest answer is yes, and the reason is that sorting solves a bigger problem than the one you were asked. Sorting puts the letters in order. You were never asked about order. You were asked about counts. You are paying for information you will throw away.
| Approach | Time | Space | Why |
|---|---|---|---|
| Remove-from-t | O(n²) | O(n) | Rescans t for every character of s |
| Sort both | O(n log n) | O(n) | Orders the letters when order is irrelevant |
| Count letters | O(n) | O(1) | Touches each character exactly once |
The reframe: count letters, compare counts
Forget code for a minute. Imagine you are doing this on paper with tally marks.
You draw 26 boxes, one for each letter a through z. You read through s and make a tally mark in the box for each letter you see. Then you read through t and erase one tally mark from the box for each letter you see.
If the two strings have exactly the same letters in exactly the same quantities, every box ends at zero. Every mark you drew got erased. If any box ends above zero, s had a letter t didn't have enough of. If any box ends below zero, t had a surplus.
That is the entire insight. Adding and subtracting the same letters cancels to nothing. No ordering, no searching, no rescanning.
And because the strings are the same length (we will check that first), you can do both passes at once — read position i of s and position i of t in the same step. Let me walk "anagram" and "nagaram" by hand. I will only show the boxes that ever move: a, n, g, r, m.
| i | s[i] adds | t[i] subtracts | a | n | g | r | m |
|---|---|---|---|---|---|---|---|
| start | 0 | 0 | 0 | 0 | 0 | ||
| 0 | a | n | 1 | -1 | 0 | 0 | 0 |
| 1 | n | a | 0 | 0 | 0 | 0 | 0 |
| 2 | a | g | 1 | 0 | -1 | 0 | 0 |
| 3 | g | a | 0 | 0 | 0 | 0 | 0 |
| 4 | r | r | 0 | 0 | 0 | 0 | 0 |
| 5 | a | a | 0 | 0 | 0 | 0 | 0 |
| 6 | m | m | 0 | 0 | 0 | 0 | 0 |
Every box is zero at the end. Return true.
Notice the counters go negative in the middle and that is completely fine. At i=0 the box for n is at -1, meaning "t has used an n that s hasn't accounted for yet." One step later s supplies it and the box settles. You only care about the final state, not the state along the way. Beginners often add an early return False the moment a counter dips negative — with the single-counter trick, that check is wrong.
Run the same table on "rat" and "car" and you end with t at +1 and c at -1. Not all zero. Return false.
The counter solution, line by line
def isAnagram(s: str, t: str) -> bool:
# 1. Different lengths can never be anagrams. Bail out immediately.
if len(s) != len(t):
return False
# 2. One tally per lowercase letter. Index 0 is 'a', index 25 is 'z'.
counts = [0] * 26
# 3. One pass. s adds a mark, t erases a mark, same position.
for i in range(len(s)):
counts[ord(s[i]) - ord('a')] += 1
counts[ord(t[i]) - ord('a')] -= 1
# 4. Perfect cancellation means every box is back to zero.
for c in counts:
if c != 0:
return False
return True
Four things happen, in this order, and each one depends on the one before it.
The length check happens first. Not for speed — for correctness of the loop that follows. Step 3 walks s and t with a single index i. If t were shorter, t[i] would crash. If t were longer, you would silently ignore its tail. The guard is what earns you the right to use one loop instead of two.
The array is created second, and its size is fixed at 26. This is where the O(1) space claim comes from. Whether the strings are 7 characters or 7 million, you allocate the same 26 integers. Space that does not grow with input size is constant space.
The counting pass is third, and ord() is the piece nobody explains. ord(c) gives you a character's numeric code: ord('a') is 97, ord('b') is 98, ord('c') is 99. Subtracting ord('a') shifts that into a 0-based slot — 'a' lands at 0, 'b' at 1, 'c' at 2, 'z' at 25. It is arithmetic that turns a letter into an array index, and it shows up in string problems constantly.
The verification pass is last. Twenty-six checks, a fixed number regardless of input, so it contributes nothing to the complexity.
Total: O(n) time — each of the n positions is touched exactly once, plus a constant 26. O(1) space — 26 integers, always.
If you would rather use a hash map (and you should, if the interviewer says the input may contain characters outside a–z):
from collections import Counter
def isAnagram(s: str, t: str) -> bool:
return len(s) == len(t) and Counter(s) == Counter(t)
Same idea, same O(n) time, but space is now O(k) where k is the number of distinct characters. Know both. Say the second one out loud in an interview and explain why you would pick it.
Common mistakes
Forgetting the length check first. This is the single most common one. Without it, the single-index loop either throws an IndexError or quietly compares only the overlapping prefix. Some people patch around it with zip() and extra conditionals; the guard is two lines and it makes everything downstream legal.
Building two full counters when one will do. Counting s into one dictionary, counting t into another, then comparing them works — but it is two passes, two allocations, and more code to get wrong. One counter that goes up for s and down for t is the same logic with half the machinery.
Checking membership instead of counts. The set(s) == set(t) version passes a surprising number of test cases and then fails on "aab" versus "abb". A set throws away exactly the information this problem is about.
Assuming lowercase ASCII when the input might be unicode. The problem statement usually promises lowercase English letters, and if it does, the 26-slot array is correct. But if it doesn't — or if the interviewer asks the follow-up, which at Goldman Sachs and ServiceNow they often do — your O(1) space claim evaporates, because unicode has far more than 26 code points. Ask before you code: can I assume lowercase a through z? Then use the hash map version if the answer is no. Asking that question is itself part of what is being scored.
Returning early when a counter goes negative. As the walkthrough showed, intermediate negatives are normal in the single-pass version. Only the final state matters.
You were probably told to grind 300 problems by someone who learned this pattern from a roommate at a school you didn't attend. You do not need 300. You need this one, understood slowly enough that the next counting problem — group anagrams, first unique character, permutation in a string — feels like the same problem wearing a different hat. It is.
Sorting rearranges the problem. Counting dissolves it.
