DSA Valid Anagram

The problem

An anagram is a word formed by rearranging the letters of another word. Two words are anagrams when they use exactly the same letters, each the same number of times. The task is to answer True or False for a pair of words.

Order does not matter. Counts do. The word aab is not an anagram of abb, even though both words use only the letters a and b.

cases = [
    ("listen", "silent", True),
    ("anagram", "nagaram", True),
    ("hello", "world", False),
    ("cat", "cats", False),
    ("aab", "abb", False),
]
for a, b, expected in cases:
    print(repr(a), "and", repr(b), "anagrams:", expected)

The fourth row fails on length alone. Words of different lengths can never hold the same letters with the same counts. The fifth row has equal lengths and the same letters present, and still fails, because the counts differ.

Intuition

The first idea most people try is sorting. Sort the letters of each word. Anagrams sort to the same string, and non-anagrams sort to different strings.

for a, b in [("listen", "silent"), ("aab", "abb"), ("hello", "world")]:
    print(a, "sorted:", "".join(sorted(a)), "|", b, "sorted:", "".join(sorted(b)), "| equal:", sorted(a) == sorted(b))

Sorting works. It is also more machinery than the question needs. Sorting rearranges a full copy of each word, and its cost grows faster than a single counting pass.

A quicker-looking idea fails outright. Comparing only which letters appear ignores counts completely. The presence test below calls aab and abb anagrams, which they are not.

a = "aab"
b = "abb"
print("same letters present:", all(ch in b for ch in a) and all(ch in a for ch in b))
print("sorted letters equal:", sorted(a) == sorted(b))

The lesson is that counts are the real content of the problem. Any correct method has to compare how many times each letter appears. Counting does that directly.

Brute force: match and cross out

The straightforward method works like crossing letters off a page. Take a copy of the second word as a list. For each letter of the first word, search the list for that letter. A found letter is removed, so it cannot be matched twice.

A letter that is not found settles the answer at once. If every letter is found and crossed out, the words are anagrams. The length check runs first, so the list is empty at the end exactly when every letter matched.

def is_anagram_brute(a, b):
    if len(a) != len(b):
        return False, 0
    pool = list(b)
    checks = 0
    for ch in a:
        found = False
        for i in range(len(pool)):
            checks += 1
            if pool[i] == ch:
                pool.pop(i)
                found = True
                break
        if not found:
            return False, checks
    return True, checks

for a, b in [("listen", "silent"), ("aab", "abb")]:
    result, checks = is_anagram_brute(a, b)
    print(a, "vs", b, "->", result, "search comparisons:", checks)

The method is correct, and its cost is visible. Each letter triggers a fresh search through what is left of the pool. Long words mean long searches, repeated for every letter.

The optimal solution: count, then cancel

The table is a Python dict. A dict holds one value for each key. In this table the keys are letters, and the value under a letter is its count so far. The line counts[ch] = counts.get(ch, 0) + 1 reads the count stored under ch, or 0 when the letter is not in the dict yet, and stores the count raised by one.

counts = {}
for ch in "aab":
    counts[ch] = counts.get(ch, 0) + 1
print(counts)

One table counts the first word up and the second word down, and the words are anagrams exactly when every count in the table ends at zero. That is the whole solution.

The length check still runs first, because different lengths settle the answer with no counting at all. The first loop adds one per letter of the first word. The second loop subtracts one per letter of the second word. A letter missing from the table subtracts from zero and ends negative, which the final zero check catches.

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

cases = [
    ("listen", "silent", True),
    ("anagram", "nagaram", True),
    ("hello", "world", False),
    ("cat", "cats", False),
    ("aab", "abb", False),
]
for a, b, expected in cases:
    print(a, "vs", b, "->", is_anagram(a, b), "expected", expected)

All five cases from the start of the article pass. Building two tables and comparing them also works. The single-table version simply cancels the counts in place instead of comparing two separate tables at the end.

Walkthrough

Watch the table for the pair aab and aba. These words are anagrams. Every count should return to zero.

counts = {}
for ch in "aab":
    counts[ch] = counts.get(ch, 0) + 1
    print("counted", repr(ch), "->", list(counts.items()))
for ch in "aba":
    counts[ch] = counts.get(ch, 0) - 1
    print("cancelled", repr(ch), "->", list(counts.items()))
print("all zero:", all(v == 0 for v in counts.values()))

The table prints in insertion order, so a appears before b. Counting aab leaves a at 2 and b at 1. Cancelling aba brings a down to 1 first, then b down to 0, then a down to 0.

Read the answer off the final table. Every value is 0. No letter is left over on either side, so the words are anagrams.

Complexity

The counting solution takes O(n) time, where n is the length of the words: it makes two passes over the letters and one short pass over the table. It takes O(k) space, where k is the number of distinct letters, because the table holds one entry per distinct letter.

def brute_checks(n):
    a = "".join(chr(ord("a") + i % 26) for i in range(n))
    b = a[::-1]
    pool = list(b)
    checks = 0
    for ch in a:
        for i in range(len(pool)):
            checks += 1
            if pool[i] == ch:
                pool.pop(i)
                break
    return checks

def counting_steps(n):
    a = "".join(chr(ord("a") + i % 26) for i in range(n))
    b = a[::-1]
    steps = 0
    counts = {}
    for ch in a:
        counts[ch] = counts.get(ch, 0) + 1
        steps += 1
    for ch in b:
        counts[ch] = counts.get(ch, 0) - 1
        steps += 1
    return steps

for n in [4, 8, 16]:
    print("length", n, "brute search comparisons:", brute_checks(n), "counting steps:", counting_steps(n))

The brute-force words here are reversals of each other, which forces long searches. Its comparison count grows roughly with the square of the length. The counting steps are exactly twice the length, one step per letter per pass.

Edge cases and pitfalls

Two empty words are anagrams. Both loops run zero times, the table is empty, and an empty table passes the zero check. One empty word and one non-empty word fail on length before any counting.

Case matters unless the problem says otherwise. The letter A and the letter a are different characters, so they get different table entries. Spaces and punctuation are characters too, and they are counted like letters.

The most common pitfall is stopping at which letters appear. The same letters present with unequal counts, like aab and abb, are the standard counterexample. A second pitfall is forgetting the early length check. Without it, the counting still answers correctly, but it does full work on pairs that one length comparison settles.

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

pairs = [("", ""), ("a", ""), ("aab", "aba"), ("Listen", "listen"), ("a b", "ba ")]
for a, b in pairs:
    print(repr(a), "vs", repr(b), "->", is_anagram(a, b))

The last pair is True because the space is a character like any other. Both words hold one space, one a and one b. Ignoring spaces would need an explicit rule in the problem statement.