Valid anagram: equality of multiplicities

Start with the meaning of equality

An anagram preserves multiplicity, the number of occurrences of each item. A set answers only presence: both aab and abb become {a, b}, so a set is an incorrect representation. A correct simple baseline sorts both strings and compares the resulting sequences. That costs O(n log n + m log m) time and O(n + m) auxiliary space in Python. Sorting solves more than required: character order is irrelevant, so store frequencies directly.

First reject unequal lengths. Build counts from the first string, then decrement for each code point in the second. Before consuming a position, each count equals its frequency in the first string minus its frequency in the consumed prefix of the second. A missing/zero count means the second requires an unavailable copy, so rejection is final. Equal lengths plus no deficit imply every initial copy was consumed; otherwise some other character would need a deficit. This is the conservation argument behind returning true without a final sort.

The improved reference takes expected O(n + m) time, O(k) auxiliary space for k distinct code points in the first string. The length rejection is O(1). Dictionary hashing is expected, not a guaranteed constant-time oracle. The strings themselves and the single boolean result are excluded from auxiliary space. Say why a fixed 26-slot array would silently change the stated alphabet.

Follow-up 1: normalize user-facing words

Ask the learner to predict the result for composed é and e plus a combining acute accent. The old contract says false. A new product requirement may say true, and case-insensitive matching may expand one input code point into several.

Specify the normalization form and transformation order before implementation; normalization and grapheme segmentation solve different problems. Count and length checks belong after the chosen transformations. The reference retains exact code-point semantics, so changing this policy requires new test fixtures.

Follow-up 2: compare enormous streams

Two iterators cannot promise cheap lengths or rewinding. Maintain signed frequency differences while consuming both streams, then check zero at both ends. Do not reject a temporary negative difference: later input can repair it.

A senior candidate explains why early rejection is valid only with the complete first-string inventory. A lead candidate defines the shared text policy and versioned compatibility across producers, plus limits for unbounded distinct symbols. A hash fingerprint can bound memory but introduces collisions; it cannot replace exact equality under this contract.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/02-valid-anagram
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def valid_anagram(first, second):
    if not isinstance(first, str) or not isinstance(second, str):
        raise ValueError("arguments must be strings")
    if len(first) != len(second):
        return False
    remaining = {}
    for char in first:
        remaining[char] = remaining.get(char, 0) + 1
    for char in second:
        if remaining.get(char, 0) == 0:
            return False
        remaining[char] -= 1
    return True

import itertools
import unittest
from solution import valid_anagram

class AnagramTests(unittest.TestCase):
    def test_exact_text(self):
        self.assertTrue(valid_anagram("", ""))
        self.assertTrue(valid_anagram("aab", "aba"))
        self.assertFalse(valid_anagram("aab", "abb"))
        self.assertFalse(valid_anagram("é", "e\u0301"))
        self.assertFalse(valid_anagram("A", "a"))
        self.assertTrue(valid_anagram("🙂 a", "a🙂 "))
        with self.assertRaises(ValueError):
            valid_anagram(None, "")

    def test_sorting_oracle(self):
        words = ["".join(chars) for n in range(4)
                 for chars in itertools.product("abé", repeat=n)]
        for first in words:
            for second in words:
                self.assertEqual(valid_anagram(first, second), sorted(first) == sorted(second))

if __name__ == "__main__":
    unittest.main()