Valid Anagram
Check whether two strings use exactly the same letters the same number of times. The standard warm-up for comparing character counts instead of sorting. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given two strings s and t. Return true if t is an anagram of s, and false otherwise.
An anagram rearranges the letters of a string: t must contain every letter of s exactly as many times as s does, and nothing else. A string is an anagram of itself.
Example 1
- Input
- s = "listen", t = "silent"
- Output
- true
Both strings have one each of e, i, l, n, s, and t.
Example 2
- Input
- s = "apple", t = "paple"
- Output
- true
Example 3
- Input
- s = "tool", t = "loot"
- Output
- true
Example 4
- Input
- s = "abc", t = "abcc"
- Output
- false
The lengths differ, so they can't be rearrangements of each other.
Constraints
- 1 ≤ s.length, t.length ≤ 5 × 10⁴
- s and t contain only lowercase English letters.
- Letter counts must match exactly, not just the set of letters.
Practice
Runs 14 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Valid Anagram in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Valid Anagram
Pattern: Character frequency counting
Two strings are anagrams exactly when their letter counts are identical. Order is irrelevant, so you only need to compare how many of each letter appear.
With a fixed alphabet of 26 letters, use one array of 26 counters. Add 1 for every letter of s and subtract 1 for every letter of t. If every counter ends at 0, the counts matched. Checking the lengths first is a cheap early exit and also means one counter going negative is enough to return false.
Approach 1: Sort and compare
Sort both strings and check whether the results are equal. Short and easy to explain, but sorting is more work than counting.
Time O(n log n) · Space O(n) for the sorted copies
Approach 2: Two hash maps
Count letters of s and t into two maps and compare the maps. Linear time and works for any alphabet, with a little more overhead than an array.
Time O(n) · Space O(k) for k distinct characters
Approach 3: One array of 26 counters
- If the lengths differ, return
false. - For each index
i, increment the counter fors[i]and decrement the counter fort[i]. - Return
trueif every counter is 0.
Doing both strings in the same loop works because the lengths are equal.
Time O(n) · Space O(1) (26 counters)
| Approach | Time | Space |
|---|---|---|
| Sort and compare | O(n log n) | O(n) for the sorted copies |
| Two hash maps | O(n) | O(k) for k distinct characters |
| One array of 26 counters | O(n) | O(1) (26 counters) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Valid Anagram solution in Python
def is_anagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
counts = [0] * 26
for a, b in zip(s, t):
counts[ord(a) - 97] += 1
counts[ord(b) - 97] -= 1
return all(c == 0 for c in counts)Valid Anagram solution in JavaScript
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const counts = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
counts[s.charCodeAt(i) - 97]++;
counts[t.charCodeAt(i) - 97]--;
}
return counts.every((c) => c === 0);
}Common mistakes
- Comparing sets of letters instead of counts, so "aab" and "abb" look like anagrams.
- Skipping the length check and then only checking that no counter goes negative, which lets "abcc" pass against "abc" in one direction.
- Assuming a 26-letter array still works when the input can contain uppercase letters, digits, or Unicode.
- Splitting a JavaScript string into UTF-16 code units when the input may hold emoji or other astral characters, which breaks them into halves. Iterate with for...of instead.
What interviewers look for
Start with sorting since it is obviously correct, name its O(n log n) cost, then improve to counting. Interviewers want to hear that anagram means "same multiset of characters" and that a fixed alphabet lets you use a constant-size array.
Mention the Unicode follow-up before you're asked; switching to a hash map is the expected answer, and noting it shows you're thinking beyond the stated constraints.
Follow-up questions
What if the inputs contain Unicode characters?
Use a hash map keyed by code point instead of a 26-slot array. In JavaScript, iterate with for...of so surrogate pairs stay together as one character. For full correctness you may also need to normalize the strings (for example to NFC) so accented letters compare equal.
How would you group a list of words into anagram groups?
Give each word a canonical key, either its sorted letters or its 26 counts joined into a string, and bucket words by key in a hash map. That is the Group Anagrams problem.
How would you find every anagram of p inside a longer string s?
Slide a window of length p.length across s while keeping letter counts for the window, adding the entering letter and removing the leaving one. Track how many of the 26 counts match p's counts so each step is O(1).
Companies that ask Valid Anagram
Valid Anagram is tagged by 110 companies in our interview dataset. The score shows how often it comes up at each company.
- Nokia100%
- Kraken Technologies95%
- Yelp94.2%
- Clear Street94%
- Viasat93%
- Boeing93%
- American Express84.4%
- Electronic Arts84%
- Mcafee84%
- Amadeus82.2%
- Springworks Therapeutics81%
- Edwards Lifesciences81%
- Epam Systems79.3%
- Mips Technologies78%
- Bloomberg75.2%
- Mastercard75%
- Corelight74%
- Check Point Software Technologies74%
- Cognizant73.2%
- Vanta73%
- Ozon72.9%
- Bitdefender72%
- Offerup72%
- Wipro70.6%
and 86 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required