032 — Valid Anagram

32 — Valid Anagram

LeetCode 242 · Easy. Given two strings s and t, return true if t is an anagram of s — that is, t uses exactly the same letters as s, the same number of times each, just possibly rearranged.

---

🍽️ Intuition

Think of two friends each dumping a bag of Scrabble tiles onto the table. To check if the bags contained the exact same tiles, you don't need to lay every tile from bag A next to a matching tile from bag B one at a time, sliding things around to find a pairing — you just sort each pile alphabetically and see if the two rows look identical. Or, even faster: count how many of each letter is in each bag and compare the tallies. If every letter count matches, the bags held the same tiles, full stop — no arranging required.

---

🚩 Pattern-Recognition Cue

"Anagram" is the giveaway word — anywhere you see it, the problem is really about comparing multiset (bag) contents, not order or position. Whenever a problem cares about "same characters, same frequency of each, order doesn't matter," reach for either sorting (to normalize both into a canonical, comparable form) or a frequency count (a hash map/array of counts). Frequency counting is almost always the faster route when the alphabet is small and known (like lowercase English letters).

---

🐢 Brute Force

Sort both strings' characters and compare the sorted results — if t is a rearrangement of s, sorting both produces identical sequences.

func isAnagramBruteForce(_ s: String, _ t: String) -> Bool {
    if s.count != t.count {
        return false
    }
    let sSorted = s.sorted()
    let tSorted = t.sorted()
    return sSorted == tSorted
}

Big-O: O(n log n) time, dominated by sorting both strings. O(n) space for the sorted character arrays.

---

🚀 Optimal

Count the frequency of each character in s, then walk t decrementing those counts. If every count lands back at exactly zero, the two strings had identical letter frequencies.

func isAnagram(_ s: String, _ t: String) -> Bool {
    guard s.count == t.count else { return false }

    var counts = [Character: Int]()
    for char in s {
        counts[char, default: 0] += 1
    }
    for char in t {
        guard let current = counts[char], current > 0 else {
            return false   // char not in s, or we've already used up all its copies
        }
        counts[char] = current - 1
    }
    return true
}

Big-O: O(n) time — two linear passes (one over s, one over t), each hash-map operation O(1) average. O(k) space, where k is the number of distinct characters (bounded by the alphabet size, so effectively O(1) for fixed alphabets like lowercase English letters).

---

🔑 The Key Insight

Sorting is a general-purpose way to normalize "same multiset, different order" into "same sequence," but it pays an log n tax to do something a hash map can do without ever reordering anything: tallying counts directly. Since we only care about how many of each character exists, not their positions, counting sidesteps sorting entirely — collapsing O(n log n) down to O(n). This is the same "count instead of compare pairwise" idea that shows up throughout hashing problems: a frequency map turns "does this match, character by character, in some order?" into "do these two tallies agree?"

---

🔗 Related Chapters

• Hash Maps & Hash Sets — the frequency-counting dictionary this solution is built on.
• Arrays & Strings — string/character traversal fundamentals.
• Big-O Notation — for comparing the O(n log n) sort against the O(n) count.
• Two Pointers — disclosed as a loose fit, not a natural one: the brute force's sSorted == tSorted in isAnagramBruteForce compares two sorted sequences as wholes with a single ==, rather than walking two sequences in tandem with explicit indices. Comparing two sorted sequences for a mismatch is the same shape Two-Pointers problems use when marching two sequences side by side — just done here with one built-in equality check instead of two explicit pointers.

---

🧸 Memory Sentence

Valid Anagram is two Scrabble bags — instead of matching tiles one by one, just count each letter and compare the tallies.

---

✅ Check Your Understanding

The optimal solution uses a single [Character: Int] dictionary, incrementing for s and decrementing for t. Would using two separate frequency dictionaries (one for s, one for t) and comparing them at the end change the Big-O in any way? Why might the single shared-dictionary approach still be preferable in practice?

---

⬅️ Previous: Contains Duplicate · Next: Two Sum ➡️