Arrays & Hashing · LC #242
Valid Anagram
Verify two strings contain the same characters at the same frequencies. Introduces the frequency-array trick for fixed alphabets and generalizes to arbitrary Unicode via hash maps.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`, and `false` otherwise. An anagram uses the same characters with the same frequencies.
Sample I/O
Input: s = "anagram", t = "nagaram" Output: true Input: s = "rat", t = "car" Output: false
Time: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
Two strings are anagrams if and only if their character frequency distributions are identical. We can encode that distribution as a length-26 integer array indexed by character offset and check for all-zeros after incrementing for s and decrementing for t.
Core Concept
Early-exit if lengths differ. Build a count array of size 26 (for lowercase ASCII). Increment count[c-'a'] for each character in s; decrement for each in t. If every count is zero the strings are anagrams. For Unicode inputs, swap the array for a hash map keyed on code-point.
When to use
Checking character-level equivalence between two strings. Building the canonical key for Group Anagrams. Any scenario requiring "same multiset of characters" - word games, spell checkers, search suggestions.
When NOT to use
When order matters (use string equality). When strings contain characters outside the assumed alphabet and you haven't switched to a hash map. When you need to identify which characters differ (a diff, not just a boolean).
Key Insights
What to Know Cold
- Length check is a fast O(1) early exit that catches most mismatches instantly.
- A fixed-size array of 26 ints is O(1) space because the alphabet size is constant, not proportional to input.
- Python's Counter equality check is the most readable one-liner but creates two dicts.
- Sorting both strings and comparing is O(n log n) - correct but suboptimal; interviewers expect the O(n) solution.
- The frequency-array key (tuple of 26 counts) is exactly the canonical key used in Group Anagrams for O(n) grouping.
1 example
Worked Examples
Frequency-Array Anagram Check
s = "anagram", t = "nagaram". Confirm they use the same letters.
Count array of 26 zeros. Increment for each char in s, decrement for each in t. All entries are zero at the end → true.
from collections import Counter
print(Counter("anagram") == Counter("nagaram")) # True
print(Counter("rat") == Counter("car")) # FalseThe frequency-map technique appears in Group Anagrams, Find All Anagrams in a String, and Minimum Window Substring - mastering it here pays off across the entire strings chapter.