Valid Anagram
Maintained by Vikas D, software engineer
You are handed two strings, s and t, both made of lowercase English letters. Return true when t is an anagram of s, and false otherwise.
Two strings are anagrams when one can be turned into the other purely by shuffling the order of its characters. Nothing is added, nothing is removed, and every letter keeps the same number of occurrences in both strings.
A quick consequence worth noticing: if the two strings have different lengths, they can never be anagrams, so that case can be rejected right away before doing any counting.
The comparison is about letter frequency, not order. "listen" and "silent" match because each holds one l, one i, one s, one t, one e, and one n, even though the letters appear in different positions.
Examples
Both strings contain three a's, one n, one g, one r, and one m, so t is a reshuffling of s.
They are the same length, but s has a t and no c while t has a c and no t, so the letter counts differ.
The lengths differ, so they cannot use the same letters the same number of times.
Constraints
- 1 <= s.length, t.length <= 5 * 10^4
- s and t consist only of lowercase English letters (a through z).
Visible test cases
- isAnagram("anagram", "nagaram") == true
- isAnagram("rat", "car") == false
- isAnagram("a", "a") == true
- isAnagram("ab", "a") == false
- isAnagram("listen", "silent") == true
- isAnagram("hello", "world") == false
Hints
Hint 1
If the strings are different lengths, you can answer false immediately without inspecting any characters.
Hint 2
Anagram status depends on how many times each letter shows up, not on where the letters sit. Think about counting letters rather than comparing positions.
Hint 3
Build a frequency tally for s, then walk through t and decrement. If any count goes negative or a leftover remains, the answer is false. Because the alphabet is fixed at 26 letters, a length-26 integer array works as the tally.
Approaches
Sort and compare
Time O(n log n) · Space O(n)Anagrams become identical once their letters are placed in a canonical order, so sorting both strings and checking equality settles the question.
- Reject early when the two lengths differ.
- Sort the characters of s into one ordered sequence and do the same for t.
- Compare the two sorted sequences position by position.
- Return true only if every position matches.
Fixed-size frequency count
Time O(n) · Space O(1)Since only 26 distinct letters are possible, a single pass that increments for s and decrements for t over a 26-slot tally tells you whether the multisets agree.
- Return false immediately if the lengths differ.
- Create an array of 26 zeros, one slot per lowercase letter.
- In one combined loop over the equal-length strings, add one for the current letter of s and subtract one for the current letter of t.
- After the loop, return true only if every slot is back to zero.
Common mistakes
- Forgetting the length check first. Without it, a short string can look balanced against a prefix of a longer one and slip through.
- Averaging or comparing characters by position instead of by count. Order does not matter, only how many of each letter exists.
- Treating the 26-slot tally as extra input-sized memory. It is a fixed 26 entries regardless of n, so the space is constant.
- Assuming uppercase or non-letter characters can appear. The inputs here are lowercase a through z, so the a-to-z offset indexing is safe, but reusing this code on mixed-case text would break that assumption.
Follow-up variations
- What changes if the strings can contain Unicode characters rather than just lowercase a through z? You would swap the fixed array for a hash map keyed by character.
- How would you handle case-insensitive or whitespace-ignoring anagrams, such as comparing whole phrases?
- Given a list of words, group all of them into sets of mutual anagrams.
- If the strings are streamed and cannot fit in memory at once, how would you compare their letter frequencies?