Week 09 — One problem, four strategies

The big question

How can four correct programs solve the same problem with very different amounts of work? This week brings the course together: define the problem, trace a program, count its work, describe its growth, and measure carefully before choosing an implementation.

The problem is anagram detection. Two strings are anagrams when they contain exactly the same characters, with the same number of occurrences of each character. Order may differ. "aab" and "aba" are anagrams; "aab" and "abb" are not. Merely containing the same kinds of letters is insufficient.

The core route is the input contract, four strategies, two worked traces, and Practices 1–2. Practice 3 and the multiplication section are optional deepening. They preserve the source lesson's further questions without adding prerequisites for Week 10.

By the end, you should explain why marking prevents reuse, why sorting hides work, why permutation generation becomes expensive, and why counting solves the fixed-alphabet problem in linear time. You should also distinguish a proved operation bound from a measured speed comparison.

Warm-up, with answers

1. Are "ab" and "aab" anagrams? No. Their lengths differ, so their multiplicities cannot all agree.
2. Are "" and "" anagrams? Yes. Both have zero copies of every character. The empty case is a valid input.
3. What is 1 + 2 + 3 + 4? 10, also 4 × 5 / 2. This triangular sum will describe checking off.
4. What does 4! mean? 4 × 3 × 2 × 1 = 24. It counts orderings of four distinct positions.
5. Is sorted(word) constant-time because it is one expression? No. The called operation processes the characters and constructs a result.

Türkçe: Anagram, yalnızca “aynı harfler var” demek değildir. Her harfin kaç kez geçtiği de aynı olmalıdır. aab ve abb aynı harf türlerini içerir fakat a ve b sayıları farklıdır. Önce doğru koşulu belirlemezsek hızlı çalışan yanlış bir çözüm üretebiliriz.

Agree on a contract before comparing costs

For the main comparison, inputs are Python strings containing only the 26 ASCII letters a through z. Uppercase letters, spaces, punctuation, accents, and Turkish characters such as ı are outside this contract. There is no automatic case conversion or removal of spaces. Unequal lengths return False; equal empty strings return True.

The counting implementation depends on this restriction. Its index is ord(letter) - ord('a'): a gives 0, b gives 1, and z gives 25. A different character can produce an invalid index or even a valid negative Python index with the wrong meaning. A real interface should validate its input or define an explicit normalization policy before calling this restricted implementation. Calling .lower() alone does not turn arbitrary Unicode text into ASCII.

Let n mean the common length after the length check. We count character comparisons or tally updates under the usual unit-cost model. “Extra space” excludes the input strings and includes temporary lists. Exact selected-operation counts are not exact counts of all Python instructions.

Strategy 1 — Find a partner and mark it used

For each character in the first string, search the second string for an unused equal character. Convert the second string to a list because Python strings cannot be changed. Replace a matched entry with None, a marker unequal to every character under our contract.

def checking_off(s1, s2):
    if len(s1) != len(s2):
        return False
    letters = list(s2)
    for letter in s1:
        found = False
        for i in range(len(letters)):
            if letters[i] == letter:
                letters[i] = None
                found = True
                break
        if not found:
            return False
    return True

assert checking_off("aab", "aba") is True
assert checking_off("aab", "abb") is False
assert checking_off("", "") is True
print("Checking-off examples passed")

break leaves only the inner search loop. found is reset for each new letter. A failed search returns immediately, because one missing occurrence is enough to reject the pair.

Worked example 1 — Repeated letters and an exact count

Trace s1 = "aab", s2 = "aba". Count each evaluation of letters[i] == letter, including comparisons against a crossed-off entry.

Total = 1 + 3 + 2 = 6. Notice that individual searches did not cost 3, then 2, then 1. The list never shrank. Instead, each successful match used a different original position. For a genuine length-n anagram, those match positions are exactly 0 through n − 1 in some order. Their search costs are therefore exactly 1 through n in some order.

Total comparisons = 1 + 2 + … + n = n(n + 1)/2. This argument works even with repeated letters. For n = 4 the total is 10; for n = 8 it is 36. The ratio 36/10 = 3.6 is near 4, not exactly 4, because the formula also contains a linear term. The worst-case time is Θ(n²), and the copied list requires Θ(n) extra space.

Türkçe: Silinen elemanın yeri listeden kaldırılmıyor; None oluyor. Bu nedenle “her turda liste bir eleman kısalır” açıklaması bu kod için yanlıştır. Üçgensel toplamın nedeni, başarılı eşleştirmede her konumun bir kez kullanılmasıdır. İşaretleme olmazsa aynı a harfini iki kez kullanıp yanlışlıkla True döndürebiliriz.

Strategy 2 — Put both strings in a common order

Sorting makes equal multisets look identical. Repeated letters are preserved: "aab" sorts to [a, a, b], while "abb" sorts to [a, b, b].

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

print(sort_and_compare("listen", "silent"))  # True
print(sort_and_compare("aab", "abb"))        # False

A usual worst-case bound for comparison sorting is O(n log n). Two sorts plus a comparison give O(n log n) + O(n log n) + O(n), hence O(n log n). The two sorted lists use O(n) extra space. The factor 2 disappears from the growth class, but the second sort still performs real work.

This is an upper-bound analysis, not a promise of exactly n log n comparisons. Python sorting adapts to existing order. Actual character distributions, repeated values, and implementation details matter. Short code can be a good engineering choice, but its cost must still be accounted for.

Strategy 3 — Generate candidates until one matches

Brute force tries arrangements of input positions. The generator yields one tuple at a time. "".join(candidate) builds a string from that tuple, and the comparison checks whether it is the target.

from itertools import permutations

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

print(brute_force("abc", "cab"))  # True
print(brute_force("aaa", "aab"))  # False; exhausts 3! candidates
print(brute_force("", ""))        # True

There are n! positional permutations. With repeated characters, different positional permutations can produce the same string: "aab" has 3! = 6 positional permutations but only 3!/2! = 3 distinct strings. This code still visits the duplicate candidates. It does not automatically remove them.

The candidate count is factorial, but the full code also joins n characters for each candidate. Exhausting the generator therefore costs Θ(n × n!) under our model. Reporting O(n!) alone describes a unit-cost-per-candidate simplification, not the full implementation. Early success may stop much sooner; worst-case statements concern inputs that force all candidates to be tried.

The generator avoids storing n! results at once. It still holds O(n) state and creates length-n candidates and strings, so auxiliary space is O(n), not O(1). Keep classroom runs very small. The examples above never exceed six candidates.

Türkçe: “Üreteç kullanmak” zaman maliyetini ortadan kaldırmaz. Üreteç bütün sonuçları aynı anda belleğe koymaz, ama gerektiğinde yine bütün adayları üretir. Ayrıca her adayın n harfini birleştirmek de iş gerektirir. Aday sayısı ile aday başına maliyeti ayrı ayrı yazmalıyız.

Strategy 4 — Count occurrences directly

Use one slot per allowed letter in each string. The exact positions no longer matter; only their totals matter.

def count_and_compare(s1, s2):
    # Contract: every character is an ASCII letter from a through z.
    if len(s1) != len(s2):
        return False
    counts1 = [0] * 26
    counts2 = [0] * 26
    for letter in s1:
        counts1[ord(letter) - ord('a')] += 1
    for letter in s2:
        counts2[ord(letter) - ord('a')] += 1
    for i in range(26):
        if counts1[i] != counts2[i]:
            return False
    return True

assert count_and_compare("aab", "aba")
assert not count_and_compare("aab", "abb")
assert count_and_compare("", "")
print("Counting examples passed")

Worked example 2 — A frequency table is a correctness argument

For "aab" and "aba", the relevant slots are:

After k characters of the first loop, its tally records exactly the occurrences in the first k characters. Initially k = 0 and every tally is zero. Processing one more character increments precisely its slot, preserving that statement. At the end, the table is correct for the whole string. The same argument applies to the second string. Comparing all slots therefore checks exactly the anagram definition.

For a true pair, selected work = n first-string updates + n second-string updates + 26 comparisons = 2n + 26. At n = 3 that is 32; at n = 1,000 it is 2,026. This excludes initialization and index arithmetic, whose inclusion does not change the linear class. A false pair may stop the final comparison before slot 25.

Two 26-slot lists occupy a fixed number of slots: O(1) extra space with respect to n in the usual word model. If alphabet size k is variable, the corresponding bounds are O(n + k) time and O(k) slots. If memory is measured in individual bits, storing increasingly large counts also matters; the constant-slot statement is not a claim of constant bits for unbounded n.

Compare evidence fairly

These are deterministic selected counts for genuine anagrams, not benchmark measurements:

The formulas establish growth; finitely many observations only support it. To measure the implementations, prepare identical valid input pairs outside the timer, check their answers, repeat, and report sizes and input family. Genuine anagrams fully exercise checking off and counting, but need not be worst-case sorting or brute-force inputs. Do not include brute force in a large-input timing loop.

Python's built-in sorting may beat a Python-level counting loop at measured sizes. These upper bounds do not guarantee that a sort/count crossover will appear in your chosen input family. Report “no crossover observed up to n = …” if that is what happened. A timing table without an actual run should be labelled illustrative, never presented as measured evidence.

For occasional short words, sorting offers a compact implementation. For a fixed alphabet and stringent time or memory needs, counting is a strong candidate. Choose using the contract, representative measurements, maintainability, and memory budget. The anagram problem is tractable; one inefficient algorithm does not make the problem intractable.

Three graduated practice problems

Practice 1 — Explain a rejection

Trace checking off for "aab" and "abb". Count comparisons and explain why reusing a match would be wrong.

Solution 1

The first a matches index 0 in one comparison. The list becomes [None, b, b]. The second a tests all three entries and fails, so the function returns False after 1 + 3 = 4 comparisons. It never processes the final b. Without marking, both a requests could reuse index 0, giving a false positive. The six-comparison formula applies to genuine length-3 anagrams, not every rejected input.

Türkçe: İkinci a için yeni bir a gerekir. Daha önce kullanılan eşleşme tekrar kullanılamaz; bu yüzden None işareti doğruluğun bir parçasıdır.

Practice 2 — Rearranged digits

Decide whether two lists containing integers 0–9 have the same multiplicities, using one tally list. Explain each phase and test an empty case, a true pair, and a false pair.

Solution 2

Add one for each occurrence in the first list; subtract one for each occurrence in the second. At the end, slot d stores “first count of digit d minus second count of digit d”. Every slot must be zero. all(...) returns True only if every generated condition is true.

def same_digits(a, b):
    # Contract: list items are integers from 0 through 9.
    if len(a) != len(b):
        return False
    balance = [0] * 10
    for digit in a:
        balance[digit] += 1
    for digit in b:
        balance[digit] -= 1
    return all(value == 0 for value in balance)

assert same_digits([], [])
assert same_digits([3, 1, 4, 1], [1, 4, 3, 1])
assert not same_digits([1, 1, 2], [1, 2, 2])
assert not same_digits([1], [1, 1])
print("Digit tests passed")

For the false equal-length pair, the final balances are +1 at digit 1 and −1 at digit 2. Time is Θ(n) in the worst case and extra space is ten slots, O(1). Türkçe: Toplama ve çıkarma iki ayrı sayacı tek bir “fark sayacı”na dönüştürür. Sıfır toplam tek başına yetmez; her kutunun sıfır olması gerekir.

Practice 3 — Optional challenge: estimate factorial growth honestly

Suppose exhaustive candidate generation at n = 9 takes one second in an illustrative constant-cost-per-candidate model. Predict n = 12 and n = 15. Then account for a cost proportional to n per candidate. Do not run those sizes.

Solution 3

The candidate-count multiplier from 9 to 12 is 12!/9! = 10 × 11 × 12 = 1,320. The prediction is 1,320 seconds = 22 minutes. From 9 to 15 it is 10 × 11 × 12 × 13 × 14 × 15 = 3,603,600, giving 3,603,600/86,400 ≈ 41.71 days.

In the full n × n! model, multiply again by the candidate-length ratio. For n = 12: 1,320 × 12/9 = 1,760 seconds, about 29.33 minutes. For n = 15: 3,603,600 × 15/9 = 6,006,000 seconds, about 69.51 days. These are model-based extrapolations, not measurements or guarantees about hardware. They also assume exhaustion, not an early successful match.

Optional deepening — Other representations and multiplication

The source's fifth implementation, collections.Counter, generalizes the tally idea using a dictionary of observed characters. For ordinary hash-table assumptions it takes expected O(n) time and O(k) space for k distinct characters. It supports more characters than the fixed ASCII table; this changes the contract. Its exact performance must be measured rather than assumed.

from collections import Counter

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

print(anagram_counter("şiş", "işş"))  # True: same exact Unicode characters
print(anagram_counter("aab", "abb"))  # False

The chapter's multiplication problems ask the same strategic question with a different input-size definition: n is now the number of digits, not the numeric value.

Repeated addition computes x × y with y additions. An n-digit base-b integer can be as large as bⁿ − 1. The running result needs at most 2n digits, so digit-by-digit addition costs O(n), not O(1). The worst-case bound is O(n × bⁿ). For fixed b, that is exponential in the input's digit length.

Grade-school multiplication pairs each of n digits with each of n digits: n² single-digit products, plus O(n²) work for carrying and adding rows. For fixed base, the total is Θ(n²).

For example, 23 × 14 = 23 × 4 + 23 × 10 = 92 + 230 = 322. The two-by-two digit multiplication uses four digit products: 3 × 4, 2 × 4, 3 × 1, and 2 × 1. Carrying and adding are additional work. Repeated addition instead adds 23 fourteen times. At twenty digits, “400” counts digit products in long multiplication, not every elementary step; the alternative can require nearly 10²⁰ additions. A smarter representation of the task changes the growth dramatically.

Türkçe: 999 sayısının değeri 999, basamak sayısı 3'tür. Girdi boyutunu 3 kabul ediyorsak 999 tekrar, boyuta göre küçük bir sabit değildir. Algoritma analizinde önce n'nin neyi ölçtüğünü söylemek bu yüzden zorunludur.

Misconceptions to repair

• “Same letters means anagram.” Count repeated occurrences as well as letter types.
• “Nested loops always mean n².” Here the exact successful count is triangular; prove the bounds from the actual searches.
• “A generator uses no growing memory.” It avoids storing all results, but its state and current candidate still grow.
• “A linear upper bound guarantees the fastest Python code.” Correctness, implementation, input family, and measured sizes still matter.
• “Four measurements prove the class.” A general count argument proves a bound; measurements test the model's relevance.

English–Turkish glossary

Readiness, repair, and the Week 10 bridge

You are ready when you can explain the repeated-letter example, name the work hidden in sorting and joining, derive 2n + 26 under the stated count convention, and choose a method with one explicit assumption. You do not need to master factorial extrapolation or digit-complexity proofs before progressing.

If matching is unclear, redraw Practice 1 and physically cross out each used position. If counts are unclear, tally "aab" and "abb" by hand before rereading the loops. If class and timing are getting mixed together, write two separate sentences: “Under this model, the bound is …” and “On these measured inputs, implementation … was faster.”

Week 10 compares data structures and the costs of their operations. Carry forward this week's main habit: a representation is useful because it makes the operations your problem needs cheaper or clearer. The array of counts worked because the question was about frequency, not order.

Count each letter, including repeats

Two words are anagrams if they contain the same letters the same number of times. First agree whether capitals and spaces count. A fast method is still wrong if it loses information needed for the answer.

Draw or trace. Lay out tiles for aab and abb. Both use letters a and b, but their piles have different sizes. Draw a per-letter tally rather than only a set of present letters.

Predict before checking. Will converting both words to sets correctly decide whether they are anagrams?

Worked reasoning

No. Both sets contain a and b, but sets discard repeat counts. Sorting keeps every letter, so we can compare the sorted words position by position. Counting letters also keeps the information we need. An array of counters needs a known, fixed set of possible letters. A dictionary can handle more kinds of keys, but its fast lookup is an average-case claim, not a worst-case guarantee.

from collections import Counter

left, right = "aab", "abb"
assert set(left) == set(right)
assert sorted(left) != sorted(right)
assert Counter(left) != Counter(right)
assert Counter("aab") == Counter("baa")
print("Sets lose the counts required by this problem.")

Change one thing. Try Aab versus baa, then a word containing a space. State whether case and spaces matter before changing capitals or removing spaces. Do not let competing methods silently solve different problems.

Türkçe: Anagramda harfin varlığı değil tekrar sayısı da önemlidir. Hız karşılaştırmasından önce bütün yöntemlerin aynı soruyu çözdüğünü doğrula.

Additional analysis laboratory

The anagram case study is valuable because all methods can be correct while their costs differ dramatically. Protect the output contract before naming a winner.

Extra exam-style prompt: Are "Dormitory" and "dirty room" anagrams? Give two possible contracts and explain why the answer changes.

Solution: Under a literal character contract including case and spaces, they are not the same multiset. Under a normalized phrase contract that ignores spaces and case, both become the same letters, so they are anagrams. Analysis must state the contract before comparing strategies.

Turkce: Ayni kelime oyunu farkli kurallarla farkli cevap verir. Bosluk, buyuk harf ve noktalama davranisi belirtilmeden hiz karsilastirmasi eksiktir.