Anagram Check —
Same letters. Different order.
Two strings are anagrams if they contain the same characters with the same frequencies — just rearranged. A hash map counts character frequencies in O(n) and comparison takes O(k). Watch the character map build on LearnBug and see exactly why "listen" and "silent" match while "hello" and "world" don't.
What is an Anagram?
Two strings are anagrams of each other if one can be rearranged to form the other. "listen" and "silent" are anagrams — same letters (l, i, s, t, e, n), same counts, different order. "rat" and "car" are not — they don't share the same set of characters. The simplest check: sort both strings and compare. The optimal check: compare character frequency maps.
Why frequency maps beat sorting
Sorting both strings takes O(n log n). Building two frequency maps and comparing takes O(n). For repeated queries on large strings, the hash map approach is significantly faster. On LearnBug you see both character maps fill up simultaneously and then compare key by key — the mismatch is immediately obvious when counts differ.
Sort → Counter → Single map
Sort and Compare — O(n log n)
Sort both strings. If they're equal after sorting — anagram. Simple but O(n log n). In Python: sorted(s1) == sorted(s2).
Counter Compare — O(n)
Build a Counter for each string and compare. Pythonic, O(n). Counter(s1) == Counter(s2).
Single Map — O(n), O(k) space ✓
One map: increment for s1, decrement for s2. All values must be 0. Saves one map's worth of space.
"listen" and "silent" — should return True
Build map for "listen" — increment each char
Decrement for "silent" — all counts go to 0
All zeros → True ✓ Anagram confirmed
"hello" and "world" — should return False
Build map for "hello", decrement for "world"
"hello"
"world"
Non-zero values → False ✓ Not an anagram
All approaches in code
from collections import Counter
# Counter comparison — cleanest
def is_anagram_counter(s1, s2):
return Counter(s1) == Counter(s2)
# Sort comparison — simple but O(n log n)
def is_anagram_sort(s1, s2):
return sorted(s1) == sorted(s2)Approach Comparison
Frequently asked questions
Does case matter in anagram detection?
By default yes — 'A' and 'a' are different characters. If the problem is case-insensitive, normalise first: s1.lower(). Similarly, if spaces should be ignored: s1.replace(' ', ''). Always clarify these constraints in an interview before coding.
How do I find all anagram positions in a string?
Use a sliding window of size len(pattern) across the string. At each position, compare the window's frequency map to the pattern's frequency map. If equal — record the position. Updating the window map as it slides is O(1) per step — total O(n). This is LeetCode 438 — Find All Anagrams in a String.
What is the LeetCode problem for anagram check?
LeetCode 242 — Valid Anagram. The follow-up asks you to handle Unicode characters — use a dict (not an array of 26) for that case. Also related: LC 438 (Find All Anagrams), LC 49 (Group Anagrams), LC 383 (Ransom Note — is one string a subset of another).
Can I use an array of 26 instead of a hash map for lowercase letters?
Yes — index by ord(c) - ord('a'). This gives O(1) access with better cache performance and no hash collision overhead. For Unicode or arbitrary characters, a dict is necessary. The array approach works only when the character set is small and known in advance.
How is anagram detection used in real applications?
Spell checkers suggest anagrams as corrections. Plagiarism detectors check if text has been rearranged. Word games (Scrabble, Wordle variants) validate words. Search engines handle query variations. Bioinformatics uses it to find DNA sequence permutations. The frequency map pattern generalises far beyond simple anagram detection.
Watch character counts fill and compare on your strings
Paste your two strings into LearnBug and see the anagram check run character by character.