You are given two strings, s and t. Return true if t is an anagram of s. An anagram is a word made by rearranging the letters of another word, using every letter exactly as many times as it appears. "listen" and "silent" are anagrams.
s = "anagram", t = "nagaram" → trues = "rat", t = "car" → falses = "aacc", t = "ccac" → false
Each string has up to 50,000 characters, and every character is a lowercase English letter from a to z.
Look closely at the third example. Both "aacc" and "ccac" use only the letters a and c. If you only checked which letters appear, you would say true. But "aacc" has two as and two cs, while "ccac" has one a and three cs. So the answer is false.
That tells us what an anagram really is. Two strings are anagrams when every letter appears the same number of times in both. The order of the letters does not matter at all. Only the counts matter.
So the question becomes: "do these two strings have exactly the same letter counts?"
The most natural first idea is to sort both strings and compare them. Sorting puts the letters in alphabetical order, so two anagrams become the same string.
Count the letters. There are only 26 possible letters, so we can keep the counts in a list of 26 numbers. Position 0 holds the count of a, position 1 the count of b, and so on up to position 25 for z.
Now here is a neat trick that saves a second list. Walk through both strings at the same time.
For each letter of s, add 1 to its count.
For each letter of t, subtract 1 from its count.
If the two strings have the same counts, every addition is cancelled by a matching subtraction. So at the end, every one of the 26 counts is zero. If any count is not zero, some letter was used a different number of times, and the strings are not anagrams.
(1) The length check. If the strings have different lengths, one of them has more letters than the other. They cannot possibly be anagrams, so we return false at once.
This line does a second job too. After it, we know both strings have the same length. That is what makes it safe for line (3) to walk both strings with one index i. Without the check, t[i] could run past the end of a shorter t.
(2) count = [0] * 26. We make a list of 26 zeros, one slot per letter. Every count starts at zero because we have not looked at any letters yet.
(3) for i in range(len(s)). We walk the positions 0, 1, 2, and so on to the last one. At each position we look at one letter of s and one letter of t.
(4) Add one for the letter of s. First we need to turn a letter into a slot number from 0 to 25. The function ord gives the number a computer uses to store a character. ord('a') is 97, ord('b') is 98, ord('c') is 99, and so on in order. So ord(letter) - ord('a') gives 0 for a, 1 for b, 2 for c, and 25 for z. Then += 1 adds one to that slot.
In TypeScript, charCodeAt(i) plays the role of ord. We store the code for 'a' once in the variable a so we do not recompute it every time.
(5) Subtract one for the letter of t. Same conversion, but this time we take one away. If t uses the same letter, it cancels the addition from s.
(6) Check that every count is zero.all(c == 0 for c in count) is True only if every one of the 26 counts is zero. A positive count means s used that letter more often than t. A negative count means t used it more often. Both mean "not an anagram", and both fail the same zero test. That is why one list is enough.
Take s = "aacc" and t = "ccac". We only show the slots for a (slot 0) and c (slot 2), because all other slots stay at zero.
i
s[i]
t[i]
count of a
count of c
start
0
0
0
a
c
1
−1
1
a
c
2
−2
2
c
a
1
−1
3
c
c
1
−1
At the end, the count of a is 1 and the count of c is −1. Not every count is zero, so the answer is false. The 1 says s had one more a than t. The −1 says t had one more c than s. That matches what we found by hand.
Time. Line (1) takes constant time. Line (2) builds 26 slots, which is also constant. The loop runs n times, where n is the length of s, and each turn does two small updates. Line (6) checks 26 slots. So the total is n times a constant, plus a constant, which is O(n).
Space. The only extra memory is the list of 26 counts. That number is 26 whether the strings have ten letters or fifty thousand. Memory that does not grow with the input is written O(1).
Be careful when you claim O(1) space. It is true only because the alphabet is fixed at 26 letters. Say that out loud in an interview. If the strings could hold any character, you would need a map with one entry per different character, and the space would be O(k), where k is the number of different characters.
Interviewers ask this one often: "What if the strings can contain any Unicode character?" Unicode is the standard list of every character in every writing system, plus emoji. It has over 150,000 characters.
Two things change.
First, a list of 26 slots no longer works. Use a map from character to count instead. In Python, Counter from the collections module builds that map for you:
python
from collections import Counterdef isAnagram(s, t): return Counter(s) == Counter(t) # compares the two count maps
Second, in JavaScript and TypeScript, string positions stop meaning "characters". A JavaScript string is stored in pieces called UTF-16 code units, and some characters, including most emoji, take two pieces. So "😀".length is 2, and s[i] can hand you half of an emoji. Loop with for (const ch of s) instead, which steps over whole characters. Python 3 does not have this problem, because len("😀") is already 1.
Group Anagrams. Put many words into groups of anagrams. The letter counts from this page become a key in a map. That is the very next page, 4.4.4.
Permutation in String and Find All Anagrams in a String. Find every place in a long string where an anagram of a short string appears. You keep this same count list for a window of the long string. As the window slides one step right, you add one letter and remove one letter. See 4.6.4.
Ransom Note. Can you build one string from the letters of another? Same counts, but now t only needs at least as many of each letter, not exactly as many.
The general lesson: when only "how many of each" matters, count instead of sort.
"Can you beat sorting?" They are checking that you notice sorting does more than the question needs. Explain that counting is O(n) and only needs 26 numbers.
"Is your space really O(1)?" They want you to say the condition: only because the alphabet has a fixed size. A common mistake is to claim O(1) for the map version too.
"Why one count list instead of two?" They are checking that you understand cancelling. Add for s, subtract for t, and any letter used differently leaves a non-zero count.
"What changes for Unicode?" A map instead of 26 slots, and in JavaScript, iterate by character, not by index.
One thing to volunteer: point out that the length check is what makes the single loop safe. It is not only a shortcut. It is the reason one index i can walk both strings.
Next:4.4.3 Two Sum. The most famous problem on the list. It uses a hash map in a third way: to store what you still need.