Anagrams and Character Frequency Maps
Solve group-anagrams, valid-anagram, and permutation-in-string using frequency arrays and hash maps for O(n) solutions.
Anagrams and Character Frequency Maps is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is an Anagram?
Two strings are anagrams if they contain the same characters with the same frequencies, just in a different order. 'listen' and 'silent' are anagrams. The simplest correctness check is sorting both strings and comparing: O(n log n). For O(n) solutions, compare character frequency maps. Anagram problems are a staple of string interviews because they test multiple techniques: hashing, sorting, and frequency arrays.
def is_anagram_sort(s, t):
return sorted(s) == sorted(t) # O(n log n)
def is_anagram_counter(s, t):
from collections import Counter
return Counter(s) == Counter(t) # O(n)
def is_anagram_array(s, t):
if len(s) != len(t): return False
freq = [0] * 26
for a, b in zip(s, t):
freq[ord(a) - ord('a')] += 1
freq[ord(b) - ord('a')] -= 1
return all(f == 0 for f in freq) # O(n)
print(is_anagram_array('anagram', 'nagaram')) # True
print(is_anagram_array('rat', 'car')) # FalseFrequency Array for Lowercase Letters
When the character set is bounded (e.g., only lowercase a-z), replace a hash map with a frequency array of size 26. Indexing by ord(c) - ord('a') maps 'a'→0, 'b'→1, ..., 'z'→25. Arrays are faster than dicts in practice due to cache locality and no hashing overhead. This trick appears in valid-anagram, anagram-permutation-in-string, and palindrome-permutation problems.
def build_freq(s):
freq = [0] * 26
for c in s:
freq[ord(c) - ord('a')] += 1
return freq
def is_anagram_fast(s, t):
return len(s) == len(t) and build_freq(s) == build_freq(t)
# Palindrome permutation: at most one odd-count character
def can_form_palindrome(s):
freq = build_freq(s)
odd_count = sum(1 for f in freq if f % 2 == 1)
return odd_count <= 1
print(can_form_palindrome('carerace')) # True ('racecar')
print(can_form_palindrome('hello')) # FalseGroup Anagrams
Group a list of strings so that all anagrams appear together. The canonical O(n×m log m) solution uses the sorted string as a hash map key. All anagrams produce the same sorted key, so they land in the same bucket. An O(n×m) variant uses a tuple of character counts as the key — slower to compute but avoids sorting entirely. The sorted-key approach is almost always preferred for clarity.
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # or ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())
words = ['eat','tea','tan','ate','nat','bat']
result = group_anagrams(words)
for g in sorted(result, key=len, reverse=True):
print(sorted(g))
# ['ate', 'eat', 'tea']
# ['nat', 'tan']
# ['bat']Anagram Key with Count Tuple
For the O(n×m) anagram grouping variant, represent each string's frequency as a tuple of 26 counts: tuple(freq_array). This avoids sorting but requires O(26×n×m) work to build all keys. Tuples are hashable in Python, making them valid dict keys. This variant is worth mentioning when the interviewer asks for 'any O(n×m) solution' — it shows understanding of different trade-offs.
from collections import defaultdict
def group_anagrams_count(strs):
groups = defaultdict(list)
for s in strs:
freq = [0] * 26
for c in s:
freq[ord(c) - ord('a')] += 1
key = tuple(freq) # tuple is hashable
groups[key].append(s)
return list(groups.values())
print(group_anagrams_count(['eat','tea','tan','ate','nat','bat']))Top K Frequent Elements
Find the k most frequent elements in an array. Counter + heap: build a frequency map in O(n), then extract the k largest frequencies using a min-heap of size k or Counter.most_common(k). An O(n) bucket sort approach creates buckets indexed by frequency (0 to n) and collects elements in reverse frequency order — elegant when k is large.
from collections import Counter
import heapq
def top_k_frequent_heap(nums, k):
freq = Counter(nums)
return heapq.nlargest(k, freq, key=freq.get)
def top_k_frequent_bucket(nums, k):
freq = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, cnt in freq.items():
buckets[cnt].append(num)
result = []
for i in range(len(buckets)-1, -1, -1):
result.extend(buckets[i])
if len(result) >= k: break
return result[:k]
print(top_k_frequent_heap([1,1,1,2,2,3], 2)) # [1, 2]
print(top_k_frequent_bucket([1,1,1,2,2,3], 2)) # [1, 2]Frequency Map for Permutation in String
Determine if any permutation of string p is a substring of s. A frequency map of a window of length |p| must equal the frequency map of p. As the window slides, increment the entering character's count and decrement the leaving character's count. Comparing two Counter objects costs O(26) each time, giving O(n×26) = O(n) overall. Track the 'formed' counter for O(1) equality check.
def check_inclusion_fast(p, s):
if len(p) > len(s): return False
need = [0] * 26
have = [0] * 26
for c in p:
need[ord(c)-ord('a')] += 1
for i in range(len(p)):
have[ord(s[i])-ord('a')] += 1
if need == have: return True
for i in range(len(p), len(s)):
have[ord(s[i])-ord('a')] += 1
have[ord(s[i-len(p)])-ord('a')] -= 1
if need == have: return True
return False
print(check_inclusion_fast('ab', 'eidbaooo')) # True
print(check_inclusion_fast('ab', 'eidboaoo')) # FalseMinimum Characters to Make Anagram
Given two strings, find the minimum number of character deletions to make one an anagram of the other. Compute frequency maps for both strings; the answer is the sum of absolute differences in frequencies. Characters present in one but absent in the other must all be deleted. This O(n) solution uses the 'merge and diff' pattern on frequency maps.
from collections import Counter
def min_steps_to_anagram(s, t):
freq_s = Counter(s)
freq_t = Counter(t)
steps = 0
# For each unique char across both strings:
all_chars = set(freq_s) | set(freq_t)
for c in all_chars:
steps += abs(freq_s.get(c, 0) - freq_t.get(c, 0))
return steps
# Or more concisely:
def min_steps_counter(s, t):
diff = Counter(s) - Counter(t)
return sum(diff.values())
print(min_steps_to_anagram('leetcode', 'practice')) # 5
print(min_steps_counter('leetcode', 'practice')) # 5Frequency Map for Ransom Note
Check if all characters in note can be supplied by characters in magazine (each magazine character can only be used once). Build a frequency map of magazine characters; then for each character in note, decrement the count. If any count goes negative, return False. This is O(n + m) time and O(1) space for lowercase-letter constrained inputs using a 26-element array instead of a dict.
def can_construct(note, magazine):
freq = [0] * 26
for c in magazine:
freq[ord(c) - ord('a')] += 1
for c in note:
freq[ord(c) - ord('a')] -= 1
if freq[ord(c) - ord('a')] < 0:
return False # insufficient supply
return True
print(can_construct('aa', 'aab')) # True
print(can_construct('aa', 'ab')) # False
print(can_construct('bg', 'efjbdfbdgbjjbghiklgdch')) # TrueLongest Anagram Substring Hashing
To check if two substrings of the same string are anagrams, use a polynomial hash of character frequencies that is commutative (order-independent). XOR of character values is commutative and O(1) to update, but has high collision probability. A better approach uses prime-product hashing (each character maps to a distinct prime; the product is order-independent). This is a niche technique for advanced interviews.
# Prime product hash: each char maps to a prime
PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,
43,47,53,59,61,67,71,73,79,83,89,97,101]
def char_hash(s):
h = 1
for c in s:
h *= PRIMES[ord(c) - ord('a')]
return h
# Two windows with equal hash are likely anagrams
print(char_hash('listen')) # same as:
print(char_hash('silent')) # should matchFrequency Map Patterns Checklist
Recognise these frequency-map interview patterns:
- Valid anagram: same length + same freq → Counter equality or array comparison
- Group anagrams: sorted string or freq tuple as dict key
- Top-k frequent: Counter + heap or bucket sort
- Permutation in string: sliding window + freq comparison
- Ransom note: freq map of supply, decrement for demand
- Palindrome permutation: at most one odd-count character
from collections import Counter
# Palindrome permutation
def palindrome_permutation(s):
return sum(v % 2 for v in Counter(s).values()) <= 1
# First unique character
def first_unique(s):
freq = Counter(s)
for i, c in enumerate(s):
if freq[c] == 1:
return i
return -1
# Character replacement for longest repeat
def char_replacement(s, k):
freq = Counter()
left = best = max_freq = 0
for right, c in enumerate(s):
freq[c] += 1
max_freq = max(max_freq, freq[c])
if (right - left + 1) - max_freq > k:
freq[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
print(palindrome_permutation('carerace')) # True
print(first_unique('leetcode')) # 0
print(char_replacement('AABABBA', 1)) # 4Odd-One-Out: XOR for Frequency
XOR is a powerful tool for frequency problems when exactly one element is odd. XOR of a number with itself cancels to 0: a XOR a = 0. XOR of all elements where every value appears an even number of times except one leaves just the odd one. This gives O(n) time and O(1) space — no hash map needed. It generalises to finding two odd-appearing numbers using XOR properties.
def single_number(nums):
result = 0
for n in nums:
result ^= n # XOR cancels pairs
return result
print(single_number([4,1,2,1,2])) # 4
print(single_number([2,2,1])) # 1
# Find the unique character in an anagram check:
def find_difference(s, t):
result = 0
for c in s + t:
result ^= ord(c)
return chr(result)
print(find_difference('abcd', 'abcde')) # 'e'Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: character frequency maps are the core tool for anagram detection — either a 26-element array for bounded alphabets or a Counter for arbitrary characters, sorted-string or freq-tuple dict keys group all anagrams together in O(n × m log m) or O(n × m) time respectively, and XOR eliminates pairs cleanly for single-element odd-count problems, providing O(n) time with O(1) space when no dict is needed. Next up we explore string encoding, reversal, and palindrome techniques.
Frequently asked questions
Is the “Anagrams and Character Frequency Maps” lesson free?
Yes — the full text of “Anagrams and Character Frequency Maps” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Anagrams and Character Frequency Maps”?
Solve group-anagrams, valid-anagram, and permutation-in-string using frequency arrays and hash maps for O(n) solutions. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Anagrams and Character Frequency Maps” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Python String API for Interviews
- Sliding Window for Substrings
- Anagrams and Character Frequency Maps
- String Encoding, Reversal, and Palindromes