Valid Anagram: count what matters

A set can tell you whether a character appears. An anagram asks a different question: does every character appear the same number of times? For that, we need counts.

The problem

Two strings are anagrams when they contain exactly the same characters with the same frequencies, possibly in a different order. This is LeetCode 242, Valid Anagram.

For example, anagram and nagaram are anagrams. rat and car are not. Two empty strings are anagrams of one another.

Why a set is not enough

The strings aab and abb have the same distinct characters, but different counts. Converting both to sets loses the information we need.

A frequency map associates each character with its count. We can add counts from the first string, then subtract counts from the second.

def is_anagram(first, second):
    if len(first) != len(second):
        return False

    counts = {}
    for char in first:
        counts[char] = counts.get(char, 0) + 1

    for char in second:
        if counts.get(char, 0) == 0:
            return False
        counts[char] -= 1

    return True

The length check matters. If both strings have the same length and we can subtract every character in the second without running out, all counts must end at zero.

With n characters and k distinct characters, the algorithm uses O(n) expected time and O(k) extra space. Under a fixed lowercase-English alphabet, k is bounded by 26. For unrestricted characters, k can grow with the input.

Walk through a small example

For aab, the map becomes {'a': 2, 'b': 1}. Reading aba reduces the counts in this order:

No count runs out early, and the lengths match. The result is True.

The sorting alternative

def is_anagram_sorted(first, second):
    return sorted(first) == sorted(second)

This is concise and easy to inspect. It takes O(n log n) time for equal-length strings and O(n) extra space for the sorted lists. Neither original string is modified.

Choose counting when frequency is the central question. Sorting is a reasonable alternative when its simplicity matters more than the additional work.

Decide what counts as a character

The example compares Python string characters exactly. It does not ignore spaces, fold case, or normalize Unicode. In a real text-processing tool, those are product decisions to make explicitly before comparing strings.

Try it yourself

Test repeated characters, empty strings, different lengths, uppercase versus lowercase, and non-English characters. Then write a function that groups a list of words into anagram families.

The reusable idea is simple: when membership loses too much information, keep a frequency map.