The problem
Given two words, decide whether one is an anagram of the other: does it use exactly the same letters, the same number of times, just in a different order?
Input: s = "listen", t = "silent" Output: true
Picture it
Picture two cloth bags of Scrabble tiles, one for each word. Tip out the first bag and count how many of each letter you have; then go through the second bag and take tiles away from those counts. If every count ends at exactly zero, the bags held the same tiles. In the picture, the tiles are letters and the tally board is a dictionary of letter → count.
How to recognise it
- Two strings must contain the same items the same number of times, in any order.
- Order does not matter, only how many of each. That is a counting question.
- The alphabet is small (26 lowercase letters on LeetCode), so a tally of counts is tiny.
- Strings can be up to 5 × 10^4 characters, so anything that rescans one string per character is too slow.
Start with brute force
Take each letter of s and cross it off a copy of t. If a letter is missing, they are not anagrams. If the lengths differ, they cannot be.
def is_anagram_brute(s, t):
if len(s) != len(t):
return False
rest = list(t)
for ch in s:
if ch not in rest:
return False
rest.remove(ch) # scans the list: O(n)
return True
Every in and remove scans the list, so time is O(n²) and space is O(n) for the copy. With n = 5 × 10^4 that is over 10^9 character comparisons in the worst case.
Sorting both strings and comparing (sorted(s) == sorted(t)) is a big step up at O(n log n), but you can do better, because only the counts matter.
From brute force to the idea
- Find the waste. The brute force searches
tagain for every letter ofs. All it really learns is how many of each letter there are. - Count once. Walk
sand add 1 to a tally for each letter. - Cancel with the other string. Walk
tand subtract 1 for each letter. If the strings are anagrams, every count ends at exactly 0. - Fail early. If a count drops below 0,
thas more of that letter thans, so returnFalseat once. - Check the length first. With equal lengths, "no count went negative" means every count is exactly 0, because the total of all counts is 0. Without the length check, extra letters in
swould go unnoticed.
This is the key idea: one tally, added to by s and subtracted from by t.
The key idea
Count letters with a dictionary (add for one word, subtract for the other). Equal counts mean an anagram, with no sorting needed.
Python solution
def is_anagram(s, t):
if len(s) != len(t):
return False
count = Counter()
for ch in s:
count[ch] += 1
for ch in t:
count[ch] -= 1
if count[ch] < 0:
return False
return TrueLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): each letter scans the rest of t | O(n): a copy of t |
| Counter (shown code) | O(n): two passes, O(1) work per letter | O(k): one entry per distinct letter, at most 26 here, so O(1) |
Edge cases
- Different lengths (
"a","ab"): returnsFalsebefore counting anything. - Same letters, different counts (
"aab","abb"): returnsFalsewhen the secondbdrives its count to −1. - Case matters (
"Ab","ab"): returnsFalse;"A"and"a"are different characters. Lower-case both strings first if the problem says otherwise. - Unicode (
"été","éét"): returnsTrue. A Counter works for any characters, which answers LeetCode's follow-up; a fixed array of 26 would not. - Two empty strings: returns
True. - Missing import: the shown code uses
Counterand needsfrom collections import Counter; without it the call raisesNameError.
Common mistakes
- Dropping the length check. Then
"aab"and"ab"returnsTrue, because no count ever goes negative. - Building two Counters and comparing only their keys (
set(s) == set(t)), which ignores how many times each letter appears. - Using
ord(ch) - ord('a')into a list of 26 when the input may contain capitals, digits or other characters.
s and t have the same length. In one step you may replace any character of t with any other character. Return the fewest steps that make t an anagram of s. For "bab" and "aba" the answer is 1; for "leetcode" and "practice" it is 5. Describe your approach, then write it if you like.
Compare with our answer
Use the same tally. Count s, subtract t. A positive count means s has that many more of a letter than t, and each of those must be produced by changing some surplus letter of t. So the answer is the sum of the positive counts.
from collections import Counter
def min_steps(s, t):
need = Counter(s)
need.subtract(t) # counts may go negative
return sum(c for c in need.values() if c > 0)
The positive and negative counts have the same total because the lengths are equal, so one change fixes one surplus and one shortage. Time O(n), space O(1) for a fixed alphabet.
A strong answer mentions: reusing the add-then-subtract tally, summing only one sign, and why one change fixes exactly one missing letter.
1. You must decide whether a ransom note can be made from a magazine's letters, using each letter at most once. Which approach fits best?
This is the anagram tally with one twist: the magazine may have extra letters, so you skip the length check and only fail when a count goes negative. Checking distinct letters ignores how many times each is needed.
2. Why is the shown code's extra space O(1) on LeetCode's inputs?
Space grows with the number of distinct characters, not with the string length. With only 26 possible letters, that is a constant. For arbitrary Unicode it would be O(k), with k the number of distinct characters.
3. A learner deletes the length check at the top of the shown code. Which call now returns the wrong answer?
With s = "aab", the count of a ends at 1, never below 0, so the function returns True. When t is the longer string, or has a letter s lacks, some count still goes negative and the answer stays correct.
Score 60% or more and the lesson is marked complete.