013. Valid Anagram

Why this mechanism works

A set loses multiplicity: aab and abb have the same set but are not anagrams. Build a supply count from a, then consume it with b. A missing supply rejects immediately. Equal lengths ensure that successful consumption cannot leave unmatched characters.

State and boundaries

counts stores unused occurrences supplied by a. Each accepted character of b consumes one occurrence.

Protocol

1. Reject unequal lengths.
2. Count every character in a.
3. For each character in b reject an exhausted supply.
4. Decrement its count.
5. Accept after all of b is consumed.

Visualization

supply aab: a=2, b=1
consume aba: a -> b -> a
remaining: a=0, b=0

Python implementation

def is_anagram(a, b):
    if len(a) != len(b):
        return False
    counts = {}
    for char in a:
        counts[char] = counts.get(char, 0) + 1
    for char in b:
        if counts.get(char, 0) == 0:
            return False
        counts[char] -= 1
    return True

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 is_anagram: if len(a) != len(b):
a='anagram'; b='nagaram'

L4 is_anagram: counts = {}
a='anagram'; b='nagaram'; counts={}

L5 is_anagram: for char in a:
a='anagram'; b='nagaram'; counts={}; char='a'

L6 is_anagram: counts[char] = counts.get(char, 0) + 1
a='anagram'; b='nagaram'; counts={'a':1}; char='a'

L5 is_anagram: for char in a:
a='anagram'; b='nagaram'; counts={'a':1}; char='n'

L6 is_anagram: counts[char] = counts.get(char, 0) + 1
a='anagram'; b='nagaram'; counts={'a':1, 'n':1}; char='n'

L5 is_anagram: for char in a:
a='anagram'; b='nagaram'; counts={'a':1, 'n':1}; char='a'

L6 is_anagram: counts[char] = counts.get(char, 0) + 1
a='anagram'; b='nagaram'; counts={'a':2, 'n':1}; char='a'

... 18 intermediate state changes omitted ...

L7 is_anagram: for char in b:
a='anagram'; b='nagaram'; counts={'a':1, 'n':0, 'g':0, 'r':0, 'm':1}; char='a'

L10 is_anagram: counts[char] -= 1
a='anagram'; b='nagaram'; counts={'a':0, 'n':0, 'g':0, 'r':0, 'm':1}; char='a'

L7 is_anagram: for char in b:
a='anagram'; b='nagaram'; counts={'a':0, 'n':0, 'g':0, 'r':0, 'm':1}; char='m'

L10 is_anagram: counts[char] -= 1
a='anagram'; b='nagaram'; counts={'a':0, 'n':0, 'g':0, 'r':0, 'm':0}; char='m'

L2 is_anagram: if len(a) != len(b):
a='aab'; b='abb'

L4 is_anagram: counts = {}
a='aab'; b='abb'; counts={}

L5 is_anagram: for char in a:
a='aab'; b='abb'; counts={}; char='a'

L6 is_anagram: counts[char] = counts.get(char, 0) + 1
a='aab'; b='abb'; counts={'a':1}; char='a'

L6 is_anagram: counts[char] = counts.get(char, 0) + 1
a='aab'; b='abb'; counts={'a':2}; char='a'

L5 is_anagram: for char in a:
a='aab'; b='abb'; counts={'a':2}; char='b'

L6 is_anagram: counts[char] = counts.get(char, 0) + 1
a='aab'; b='abb'; counts={'a':2, 'b':1}; char='b'

L7 is_anagram: for char in b:
a='aab'; b='abb'; counts={'a':2, 'b':1}; char='a'

L10 is_anagram: counts[char] -= 1
a='aab'; b='abb'; counts={'a':1, 'b':1}; char='a'

L7 is_anagram: for char in b:
a='aab'; b='abb'; counts={'a':1, 'b':1}; char='b'

L10 is_anagram: counts[char] -= 1
a='aab'; b='abb'; counts={'a':1, 'b':0}; char='b'

Why the solution is correct

Counts begin as the exact multiset of a. Every decrement matches one distinct occurrence. Failure proves a multiplicity mismatch; success after equal-length consumption matches every supplied occurrence exactly once.

Time and space

O(n+m) expected time and O(u) space for u distinct characters.

Common mistakes

Comparing sets ignores repeated letters. Accidentally lowercasing changes the stated contract.

Reasoning card

Transfer exercise

Return the minimum deletions across both strings needed to make their character multisets equal.