Anagrams and Character Frequency Maps
Solve group-anagrams, valid-anagram, and permutation-in-string using frequency arrays and hash maps for O(n) solutions.
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')) # FalseAll lessons in this course
- Python String API for Interviews
- Sliding Window for Substrings
- Anagrams and Character Frequency Maps
- String Encoding, Reversal, and Palindromes