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!) 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 will assume lower-case letters only.

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:

T(n) ≈ n + (n−1) + (n−2) + … + 1 = n(n+1)/2  →  O(n²)

Correct, readable, and the shape you should now recognise instantly — a nested loop over the same data.

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). 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. It is also useless, and the reason is arithmetic rather than programming. A word of n letters has n! (n factorial) arrangements:

A twenty-letter word would outlast your career, your institution, and — at n = 25 — the age of the universe. This is what people mean when they say a problem is intractable: not "we need a faster machine", but "no machine that could ever exist would finish". Try it at n = 8 to feel it move, and never again.

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):                        # always 26 steps
        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 a fixed 26 comparisons:

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

Linear — the best possible, since any correct method must at least look at every letter. 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):
    """Two strings of length n that really are anagrams — the 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")

Two things to notice. First, the speedup column grows — at n = 4 000 the naive method is already 600 times worse, and it will be 6 000 times worse at n = 40 000. Second, the sort version beats the counting version in wall-clock time even though its class is worse, because sorted() runs in optimised C while your counting loop runs in Python. That is a constant factor at work — and it is exactly why we measure as well as classify.

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. There is a cleaner way to prove a class: count the fundamental operations the algorithm performs and watch how the count grows. If the theory says O(n²), then doubling n should roughly quadruple the count; if it says O(n), doubling should roughly double it. No stopwatch required.

We add a counter to each method — for the two loop-based ones we count letter comparisons; for the counting method we count tally updates plus the 26 final checks. 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):
    ops = 0
    letters = list(s2)
    for letter in s1:
        for i in range(len(letters)):
            ops += 1                         # one comparison
            if letters[i] == letter:
                letters[i] = None
                break
    return ops

def count_ops(s1, s2):
    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
    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

Read the two ratio columns and the classes fall straight out. Checking-off quadruples with every doubling — the unmistakable fingerprint of O(n²), and the raw counts sit right on the predicted n²/2. Counting doubles with every doubling — O(n), sitting on the predicted 2n + 26. This is the same ratio-column reasoning you used with the doubling harness in weeks 5–7, applied to operation counts instead of seconds, and it is immune to a noisy laptop.

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 — the memory does not grow with n, so this is O(1) extra space, unlike the sorted copies solution 2 must build.

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 the only responsible choice — its linear time and constant extra space are the difference between "instant" and "times out". The professional answer is not a single winner; it is "solution 2 by default, solution 4 when the numbers say so, and here is the number that flips it" — the crossover you will find in the homework.

9.9Try it yourself

from collections import Counter

def anagram_counter(s1, s2):
    return Counter(s1) == Counter(s2)

def same_multiset(a, b):
    if len(a) != len(b):
        return False
    counts = [0] * 10          # one slot per digit 0-9
    for x in a:
        counts[x] += 1
    for x in b:
        counts[x] -= 1         # cancel out
    return all(c == 0 for c in counts)

9.10Self-check

9.11Homework

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.