Are two words anagrams?
You're given two strings s and t made of lowercase English letters. Return
true if t uses exactly the same letters as s, with each one turning up the
same number of times, and false if it doesn't.
Examples
| Input | Output | Why |
|---|---|---|
s = "anagram", t = "nagaram" | true | |
s = "rat", t = "car" | false | |
s = "aab", t = "abb" | false | They've got the same letters, but not the same number of each. |
Constraints
- 0 ≤ s.length, t.length ≤ 5 × 10⁴
- s and t contain only the letters a to z
Hints
Hint 1
If you sort both strings and compare them, that works in O(n log n). What does sorting tell you that you don't need to know?
Hint 2
Count how often each letter turns up in s, then do the same for t, and compare the two lots of counts.
Hint 3
You can get away with one table. Add 1 for each letter of s and take 1 off for each letter of t, and if they're anagrams you'll be left with 0 everywhere.
Where people lose marks
- Comparing the sets of letters. "aab" and "abb" have the same set, but you'll see they don't have the same counts.
- Building two tables and comparing them key by key, and then missing a letter that's in only one of them.
- Leaving out the length check. The table on its own still gets it right, so this won't cost you the answer, but you've thrown away an early exit that's free.
Dry run on "aab","aba"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7sa0a1b2ta0b1a2count[a]1
s[0] = a: count[a] goes up to 1.
-
Step 2 / 7sa0a1b2ta0b1a2count[a]2
s[1] = a: count[a] goes up to 2.
-
Step 3 / 7sa0a1b2ta0b1a2count[a]2count[b]1
s[2] = b: count[b] goes up to 1.
-
Step 4 / 7sa0a1b2ta0b1a2count[a]1count[b]1
t[0] = a: count[a] goes down to 1.
-
Step 5 / 7sa0a1b2ta0b1a2count[a]1count[b]0
t[1] = b: count[b] goes down to 0.
-
Step 6 / 7sa0a1b2ta0b1a2count[a]0count[b]0
t[2] = a: count[a] goes down to 0.
-
Step 7 / 7sa0a1b2ta0b1a2count[a]0count[b]0
Every count is back to 0: the words are anagrams.
How to think about it
This is the problem that's usually listed as Valid Anagram.
Sorting both strings and comparing them gives you the right answer, and it does more work than you need to. It puts the letters in order, when all you want to know is how many of each there are, and a table of counts will tell you that in one pass.
With only 26 possible letters, the table can be an array of 26 integers. You can think of it as a hash map
whose hash function is c − 'a', so it never has a collision. We add 1 for every letter of
s and take 1 off for every letter of t, and the two words are anagrams if, and only
if, all of the counts are back to 0 by the end. It's worth checking the lengths first: if they're different,
you can say no straight away.
If the text can be any Unicode, you'd use a real hash map keyed on the character, and the rest of the logic stays as it is.
Complexity. Time O(n) · Space O(1), 26 counters
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def is_anagram(s, t):
if len(s) != len(t):
return False
count = [0] * 26
for a, b in zip(s, t):
count[ord(a) - 97] += 1 # up for s
count[ord(b) - 97] -= 1 # down for t
return all(c == 0 for c in count)#include <string>
using namespace std;
bool solve(const string& s, const string& t) {
if (s.size() != t.size()) return false;
int count[26] = {0};
for (size_t i = 0; i < s.size(); ++i) {
count[s[i] - 'a']++; // up for s
count[t[i] - 'a']--; // down for t
}
for (int c : count) if (c != 0) return false;
return true;
}class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++; // up for s
count[t.charAt(i) - 'a']--; // down for t
}
for (int c : count) if (c != 0) return false;
return true;
}
}function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++; // up for s
count[t.charCodeAt(i) - 97]--; // down for t
}
return count.every(c => c === 0);
}fn solve(s: &str, t: &str) -> bool {
if s.len() != t.len() { return false; }
let mut count = [0i32; 26];
for (a, b) in s.bytes().zip(t.bytes()) {
count[(a - b'a') as usize] += 1; // up for s
count[(b - b'a') as usize] -= 1; // down for t
}
count.iter().all(|&c| c == 0)
}import qualified Data.Map.Strict as M
solve :: String -> String -> Bool
solve s t = length s == length t && all (== 0) (M.elems counts)
where
-- +1 for each letter of s, -1 for each letter of t
counts = M.fromListWith (+) ([(c, 1 :: Int) | c <- s] ++ [(c, -1) | c <- t])
Variants to try
- How would you put a list of words into groups of anagrams? (You'd key a map on the sorted word, or on its 26 counts.)
- Can you find every place in a text where an anagram of a given word begins? (You'd slide a window of fixed length along it and carry the same table with you.)
Next problems
The k most frequent values
A hash map does the counting in one pass. The interesting part is ordering what you counted, and saying precisely how ties break.
Open the problem → Medium20 minGroup the words that are anagrams
Two words are anagrams when they have the same letter counts, so the whole trick is to turn each word into a key that depends on nothing else and then let a hash map do the grouping for you.
Open the problem → Easy10 minCut a note out of a magazine
You count the letters the magazine gives you and then spend them on the note one at a time, and the first count that would go below zero tells you the answer is no.
Open the problem →Write a solution and run it against the real test table.
Keep going
The k most frequent values
A hash map does the counting in one pass. The interesting part is ordering what you counted, and saying precisely how ties break.
Open the problem → Medium20 minGroup the words that are anagrams
Two words are anagrams when they have the same letter counts, so the whole trick is to turn each word into a key that depends on nothing else and then let a hash map do the grouping for you.
Open the problem → Easy10 minCut a note out of a magazine
You count the letters the magazine gives you and then spend them on the note one at a time, and the first count that would go below zero tells you the answer is no.
Open the problem → Arrays and hashingThe pattern behind it
Trade memory for time: a hash map answers "have I seen this?" in O(1), and most array problems reduce to asking it the right question.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.