One Problem, Four Algorithms: The Anagram Story

9.1The problem

Two words are anagrams if one is a rearrangement of the other: "listen" and "silent"; "python" and "typhon". Write a function that takes two strings of the same length and returns True if they are anagrams.

It sounds trivial, and it is — the answer is easy to get right. What makes it the perfect teaching example is that four natural, correct approaches land in four different complexity classes. Same problem, same computer, same programmer: O(n²), O(n log n), O(n · n!) for the full brute-force code, and O(n).

For all four we will use the length of the words as n, and to keep the focus on the idea we assume only ASCII letters a–z. The 26-slot implementation does not support arbitrary Unicode lowercase characters, spaces or punctuation. It requires validation or an explicit normalization policy at a real interface. Unequal lengths return False; two empty strings are anagrams.

9.2Solution 1 — checking off

The way most people describe it out loud: take each letter of the first word and cross it off in the second; if every letter finds a partner, they are anagrams.

def anagram_checking_off(s1, s2):
    if len(s1) != len(s2):
        return False

    letters = list(s2)                # we need to cross letters off
    for letter in s1:
        found = False
        for i in range(len(letters)):     # search for a partner
            if letters[i] == letter:
                letters[i] = None         # cross it off
                found = True
                break
        if not found:
            return False
    return True

print(anagram_checking_off("listen", "silent"))   # True
print(anagram_checking_off("listen", "silence"))  # False

The cost. For each of the n letters of s1 we scan up to n positions of letters. That is a loop inside a loop, both over n:

For a genuine anagram: comparisons = 1 + 2 + … + n = n(n+1)/2  →  Θ(n²)

The list does not shrink: crossed-off entries are still inspected. On a genuine anagram, each original position is matched once, so the successful search lengths are exactly 1 through n in some order, even with repeated letters. Rejections may stop earlier. Worst-case time is Θ(n²); the list copy uses Θ(n) extra space.

9.3Solution 2 — sort and compare

A neat observation: two words are anagrams exactly when their letters, sorted, are identical. So sort both and compare.

def anagram_sort(s1, s2):
    if len(s1) != len(s2):
        return False
    return sorted(s1) == sorted(s2)

Three lines, obviously correct, and it looks free — which is the trap. The work has not disappeared, it has moved inside sorted(), which is O(n log n) in a usual worst-case comparison-sort bound. Python’s adaptive sorting can do less work on particular inputs. The final comparison is O(n). Adding them and keeping the dominant term:

O(n log n) + O(n) → O(n log n)

Better than solution 1 and much shorter to write. This is the "sensible default" answer, and in most real work it is the right one.

9.4Solution 3 — brute force (do not run this on long words)

The "try everything" approach: generate every possible rearrangement of the first word and check whether the second appears among them.

from itertools import permutations

def anagram_brute_force(s1, s2):
    if len(s1) != len(s2):
        return False
    for candidate in permutations(s1):
        if "".join(candidate) == s2:
            return True
    return False

It is correct, but exhaustive enumeration becomes impractical quickly. A word of n positions has n! positional permutations. Repeated characters create duplicate strings that permutations still emits. The table assumes an illustrative ten million candidates per second, not a measured rate:

At that hypothetical rate, exhaustive enumeration becomes impractical for large n. The anagram problem is tractable because efficient alternatives exist. For this code, joining each candidate costs Θ(n), making exhaustive worst-case time Θ(n · n!), not O(n!) under a full character-operation count. Early success may stop much sooner. The generator avoids storing every result, but its state and current candidate use O(n) extra storage. Keep experimental runs at very small n.

9.5Solution 4 — count and compare

The winning move is to stop comparing letters with letters. Count how many times each letter occurs in each word, then compare the two tallies.

def anagram_count(s1, s2):
    if len(s1) != len(s2):
        return False

    counts1 = [0] * 26          # one slot per letter a-z
    counts2 = [0] * 26

    for letter in s1:                          # n steps
        counts1[ord(letter) - ord('a')] += 1
    for letter in s2:                          # n steps
        counts2[ord(letter) - ord('a')] += 1

    for i in range(26):                        # up to 26 checks; all 26 for anagrams
        if counts1[i] != counts2[i]:
            return False
    return True

ord('a') is 97, ord('c') is 99, so ord(letter) - ord('a') turns a letter into a slot number 0–25. Two passes over the words, then up to 26 comparisons. For a genuine pair, counting only tally updates and final comparisons gives exactly:

T(n) = 2n + 26  →  O(n)

Linear in the worst case — optimal in this character-access model, because a correct method must inspect all characters on some inputs. This need not happen on an early rejection. Notice what paid for it: extra memory (two lists of 26) and a cleverer question ("how many of each?" instead of "does this one match?"). That trade — spend a little space to save a lot of time — is one of the most reliable moves in all of computing, and week 11 is built entirely on it.

9.6Head to head

Now measure it yourself rather than trusting the table. Long "words" made of random letters stand in for real ones:

import random, string, time

def make_pair(n):
    """Genuine anagrams; full checks for checking-off/counting, not every method’s worst case."""
    letters = [random.choice(string.ascii_lowercase) for _ in range(n)]
    shuffled = letters[:]
    random.shuffle(shuffled)
    return "".join(letters), "".join(shuffled)

def time_call(func, s1, s2, repeats=3):
    best = None
    for _ in range(repeats):
        start = time.perf_counter()
        func(s1, s2)
        t = time.perf_counter() - start
        if best is None or t < best:
            best = t
    return best

for n in [500, 1000, 2000, 4000]:
    s1, s2 = make_pair(n)
    a = time_call(anagram_checking_off, s1, s2)
    b = time_call(anagram_sort, s1, s2)
    d = time_call(anagram_count, s1, s2)
    print(f"n={n:>5}  checking-off {a:.5f}s   sort {b:.5f}s   count {d:.5f}s   speedup {a/d:,.0f}x")

The displayed timings illustrate possible output; run the code for measurements on your machine. A quadratic-versus-linear model predicts a growing speedup, but the particular factor at n = 40 000 must be measured or labelled as an extrapolation. Built-in sorting may outperform Python-level counting over a measured range because implementation constants and input structure matter. Record those conditions.

9.7Counting operations to confirm the class

Timing is honest but noisy — it mixes in your CPU, the language and whatever else the machine is doing. A code-derived general operation formula can prove a bound under its model. Instrumented counts test that derivation at selected sizes. A tight quadratic model has ratios approaching four; a tight linear model has ratios approaching two. A table of a few ratios cannot prove how the work grows for all large inputs.

For checking off we count letter comparisons; for counting we count tally updates plus the final checks (all 26 on genuine anagrams). These selected operations exclude initialization and indexing arithmetic; they are not full Python instruction counts. Because anagram_sort hides its work inside C, we time it separately in the benchmark; here we compare the two we can instrument.

import random, string

def make_pair(n):
    letters = [random.choice(string.ascii_lowercase) for _ in range(n)]
    shuffled = letters[:]
    random.shuffle(shuffled)
    return "".join(letters), "".join(shuffled)

def checking_off_ops(s1, s2):
    if len(s1) != len(s2):
        return 0
    ops = 0
    letters = list(s2)
    for letter in s1:
        found = False
        for i in range(len(letters)):
            ops += 1                         # one comparison
            if letters[i] == letter:
                letters[i] = None
                found = True
                break
        if not found:
            return ops
    return ops

def count_ops(s1, s2):
    if len(s1) != len(s2):
        return 0
    ops = 0
    c1 = [0] * 26
    c2 = [0] * 26
    for letter in s1:
        c1[ord(letter) - ord('a')] += 1; ops += 1
    for letter in s2:
        c2[ord(letter) - ord('a')] += 1; ops += 1
    for i in range(26):
        ops += 1
        if c1[i] != c2[i]:
            return ops
    return ops

print(f"{'n':>6}  {'checking-off':>14}  {'ratio':>6}   {'count':>8}  {'ratio':>6}")
prev_a = prev_c = None
for n in [250, 500, 1000, 2000]:
    s1, s2 = make_pair(n)
    a = checking_off_ops(s1, s2)
    c = count_ops(s1, s2)
    ra = "-" if prev_a is None else f"{a/prev_a:.1f}x"
    rc = "-" if prev_c is None else f"{c/prev_c:.1f}x"
    print(f"{n:>6}  {a:>14,}  {ra:>6}   {c:>8,}  {rc:>6}")
    prev_a, prev_c = a, c

For these genuine anagrams, the counts are exactly n(n+1)/2 and 2n+26. The first doubling ratio approaches four and the second approaches two; neither is exactly its limiting value at every n. The formulas justify Θ(n²) and Θ(n), and the table checks the implementation. These counts are deterministic for this input family and do not depend on stopwatch noise.

9.8Which would you ship?

"Fastest class" is not automatically "best choice". Real decisions weigh speed against readability, memory, and the size of the data you will actually see. Line the four up against those questions and the answer stops being obvious:

* Two fixed 26-slot lists give O(1) slots under the word model. If alphabet size k varies, initialization and comparison cost O(k), total time is O(n+k), and extra space is O(k). Bit-level storage also depends on the size of the integer counters.

So which do you ship? For a word game where inputs are a dozen letters and the check runs occasionally, solution 2 is the right call: one line, obviously correct, fast enough that its worse class never bites. For a bioinformatics tool comparing million-character sequences, or a service that runs the check millions of times a second, solution 4 is a strong candidate when the input uses the fixed set of letters the method allows: it has linear worst-case time and constant extra slots. Validate its implementation and measure representative inputs against the actual latency and memory requirements. The professional answer is not a single winner; it is "solution 2 by default, solution 4 when the requirements and evidence support it". A crossover may or may not appear in the optional extension’s tested range.

9.11Optional Studio Extension

9.12Words from this week

9.13Chapter problem set — Skiena 2.10

These two problems from Skiena's The Algorithm Design Manual ask exactly the question week 9 keeps asking — two correct methods, two wildly different costs — but about a problem every child already knows: multiplying two numbers. Read each restated problem, have a go, then open the worked solution.