Character Arithmetic & Count Arrays

Characters as numbers

Every string algorithm eventually touches character codes — a computer stores letters as numbers, and these functions move between the two. The bridge functions:

ord("a")             # 97 — character to code point
chr(98)               # "b" — code point to character
ord("c") - ord("a")   # 2 — letter's alphabet position

Because a–z sit on one unbroken run of consecutive codes, subtracting ord("a") from any lowercase letter's code gives that letter's position in the alphabet, starting at 0 — that's what makes ord(ch) - ord("a") a safe array index.

The count array

The payoff is the count array: when constraints promise "lowercase English letters," 26 integer slots replace a whole hash map — smaller, faster, and O(1)-iterable, since 26 never grows with the input:

def letter_counts(s: str) -> list[int]:
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    return counts

Trace it on s = "cab", starting from counts = [0, 0, 0, ..., 0] (26 zeros):

Three characters, three O(1) index computations, done — the final array says "one a, one b, one c," regardless of what order they arrived in.

Why a count array beats a hash map here

The lesson isn't "arrays are always faster" — it's that a hash map is paying for generality this problem doesn't need, in three concrete ways:

1. Allocation. A hash map dynamically allocates buckets, resizes them as entries grow, and handles collisions (Hash Tables module). A count array is one fixed block of 26 slots, sized once.
2. Per-operation cost. A hash map insert computes a hash function before it can even find a bucket. A count array "insert" is one subtraction (ord(ch) - ord("a")) and one array write — no hashing step exists to pay for.
3. Iteration. Iterating a hash map visits however many distinct keys are present — that count can grow with the input. Iterating a count array always visits exactly 26 slots, no matter how long the input string is. Because 26 is a fixed constant, that iteration is O(1), not O(number of distinct characters).

A count array is a frequency fingerprint: if two strings produce identical counts, they contain exactly the same letters the same number of times each — which is exactly what it means for one to be a rearrangement of the other, and rearranging can't change those counts either way. So matching fingerprints isn't just a good sign, it's a complete test. The Valid Anagram problem is this observation and nothing more; the Hash Tables module generalizes it to unrestricted alphabets, where a fixed 26-slot array stops being practical.

Next: the string's own standard-library methods — what they actually cost, and the two-pointer idioms that recur across string problems.