Letter counting with 26-slot lists in Python

Why this matters

A string is a row of characters. Often the order of the characters does not matter. What matters is how many times each letter appears. Two words that use the same letters the same number of times are anagrams. "listen" and "silent" are anagrams. "listen" and "lister" are not, because "lister" has an r where "listen" has an n.

Anagram checks, letter-tile games and simple spell checks all use one step: count how many times each letter appears. This lesson shows how to do that count fast with a list of 26 slots, one slot for each letter from a to z.

The lesson uses the idea that a character is a number. You will use that idea again in the Caesar cipher lesson that follows. Other lessons in this module cover splitting text into fields, searching for a smaller string inside a larger one, and characters outside the basic letters, such as emoji.

Characters are numbers

Python stores each character as a number, called its code point. The built-in function ord returns the number for a character, and chr returns the character for a number. For the letters we need here, the numbers go in order. ord("a") is 97, ord("b") is 98, and so on up to ord("z"), which is 122. Capital letters have their own numbers. ord("A") is 65 and ord("Z") is 90.

You can see the numbers directly:

The output is:

97
98
b
2

The third line shows a detail to remember. When you add a number to ord("a"), Python does the arithmetic on the number, so ord("a") + 1 is 98. To get a character back, you pass the number to chr.

The last line is the one this lesson depends on. The distance from "a" to "c" is 2. Subtracting ord("a") from any lowercase letter gives its position in the alphabet, starting at 0. So ord("a") - ord("a") is 0, ord("b") - ord("a") is 1, and ord("z") - ord("a") is 25. That gives 26 positions in total, which is why the list has 26 slots.

The idea, with an everyday example

Picture a wall of 26 mailboxes, labelled A to Z. You hold a letter in your hand, and you go through the word one letter at a time. Each time you see a letter, you put one card in the box with that letter's label. When you are done, each box holds the number of times its letter appeared.

Count the word banana this way. Start with all boxes empty.

• The first letter is b. Put a card in box b. Now b has 1.
• The second letter is a. Put a card in box a. Now a has 1.
• The third letter is n. Put a card in box n. Now n has 1.
• The fourth letter is a. Put a card in box a. Now a has 2.
• The fifth letter is n. Put a card in box n. Now n has 2.
• The sixth letter is a. Put a card in box a. Now a has 3.

At the end, a has 3, b has 1, n has 2, and every other box is empty. The list does the same job. The slot for each letter is found by subtracting ord("a"), so you never need to search for the right box.

The counting loop, step by step

Here is a function that counts the lowercase letters in a word. It returns the list of 26 counts.

The output is:

[3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

A few parts need explaining. [0] * 26 makes a list of 26 zeros. The loop for ch in word visits each character in order, so you do not need an index. The expression ord(ch) - ord("a") turns the letter into its slot number. The += 1 adds one to the value stored in that slot.

Trace the function on banana. Each row shows the letter, its slot number, and the value in that slot after the step.

1. b goes to slot 1. Slot 1 becomes 1.
2. a goes to slot 0. Slot 0 becomes 1.
3. n goes to slot 13. Slot 13 becomes 1.
4. a goes to slot 0. Slot 0 becomes 2.
5. n goes to slot 13. Slot 13 becomes 2.
6. a goes to slot 0. Slot 0 becomes 3.

The printed list starts at slot 0. Slot 0 holds 3, slot 1 holds 1, and slot 13 holds 2. Every other slot holds 0.

To find the count for one letter, use the same subtraction. The count for n is counts[ord("n") - ord("a")], which is counts[13]. The program below prints it:

The output is:

2

Checking two words for equal counts

Once you have a count list for each word, comparing them is the anagram check. Two words are anagrams when their count lists are equal. In Python, == on two lists compares every item in order, and it returns True only when all of them match.

The output is:

True
False

The word listen has one i and one s, and so does silent. Every other letter also matches. The word lister has an r where listen has an n, so the slots for n and r differ.

Python lists compare by content, so this check is correct. Two different lists with the same numbers are equal with ==. This is different from some other languages, where == on arrays compares object identity. The rule from the first lesson still holds for objects in general: is asks whether two names point to the same object, and == asks whether the contents match.

Real text: capital letters, spaces and punctuation

The function above works only when every character is a lowercase letter from a to z. Real text has capitals, spaces, commas and digits. A capital L has the number 76, so ord("L") - ord("a") is -21. A space has the number 32, so ord(" ") - ord("a") is -65. The two results behave differently in Python, and the difference is the easiest part of this lesson to miss.

A negative index in a Python list counts from the end. Index -21 in a list of 26 items is the same as index 5. So a capital L does not raise an error. It silently adds one to the slot for f, which is the sixth letter. Here is the proof:

The output is:

[0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]

The first list has a 1 in slot 5, which is the letter f. The word Listen has no f. The error is silent, so the output looks like a normal count. A space is different, because -65 is further from the end than the list is long, so Python raises an error for it:

The output is:

IndexError: list index out of range

A character with a larger code, such as the curly brace {, has code 123 and gives index 26, which is past the end of the list. Python raises the same IndexError. The safe fix is the same in every case: skip any character that is not a lowercase letter. The version below checks the range before it counts:

The output is:

[1, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0]

The condition "a" <= ch <= "z" is a chained comparison. It means the character is at least "a" and at most "z". Python compares single-character strings by their code points, so this test works without calling ord. Spaces, digits, punctuation and capital letters all fail the test and are skipped.

For an anagram check on phrases, you also need to ignore capitals. The simplest way is to change the whole string to lowercase first with lower(). Unlike some languages, Python's lower() does not depend on the language setting of the computer, so the result is the same on every machine for plain English text.

The output is:

True
True
False

The second phrase in each of the first two pairs has a space. The spaces are skipped, and the capitals are made lowercase first. Both phrases then count the same way. "Dormitory" has 9 letters, and "Dirty room" has 9 letters and a space, so once the space is skipped the counts match.

A second example: the most common letter

Counting letters is useful for more than comparisons. This function finds the letter that appears most often in a text. It reads the count list and keeps the slot with the highest value.

The output is:

o

This function runs the reverse of the counting step. The slot number best is turned back into a letter by adding it to ord("a") and passing the result to chr. This works because ord("a") + 3 is the code for d, the fourth letter, and the slot number for d is 3.

The line counts[i] > counts[best] uses a strict greater-than. If two letters have the same count, the first one in the alphabet keeps its place. This is a choice you should know about, because another rule, such as "the last one wins," would change the answer.

The letter o appears four times in the sentence, in brown, fox, over and dog. The letter e appears three times, so o wins. The standard library's collections.Counter does this count in one line, with Counter(text).most_common(1). That version counts any character, not only the 26 letters, which is why the explicit list is better for learning the idea.

A third example: letters that appear exactly once

This example combines a count with a condition. It counts how many letters appear exactly once in a word. This kind of check is useful when you look for a letter that is unique in a list of candidates.

The output is:

1
1

The loop for n in counts reads every slot in order and gives you its value as n. It does not give you the slot number. When you need the number, use for i, n in enumerate(counts).

The word aabbc has a twice, b twice and c once. So count_singles("aabbc") returns 1. Only c is a single. The word mississippi has m once, i four times, s four times and p twice. Only m is a single, so the answer is 1.

A fourth example: can one word be built from another

A harder use of the same counts is the "ransom note" check. You are given a note and a source text. Can the note be written using only the letters in the source, with each source letter used at most once? The count list makes this simple. Count the source. Then, for each letter of the note, take one from that letter's slot. If the slot is already 0 when a letter is needed, the note cannot be built.

The output is:

True
False
True
False
True

The list available changes as the loop runs, so each source letter is used only once. The note aa needs two a letters, and aab has two. The note aaa needs three, and aab has only two, so the result is False. The note Bob needs two b letters, but bo has only one, so the result is False. The empty note needs no letters, so the result is True.

Why a list and not a dict

A dict stores a key and a value for each entry, such as the letter "a" and its count. A dict can count any character, including capitals and digits, and it does not need the range set in advance. The 26-slot list is the better fit for this lesson for two reasons. Its size never changes, so there is nothing to grow or resize. And each slot is found by one subtraction, so the code shows the alphabet directly. A dict is the right choice when the set of keys is large or not known in advance. The collections.Counter class is a dict for counting, and it is the usual choice in real code.

Common mistakes

The mistakes below are the ones beginners make most often. Each one shows the real error message from running the code, or the silent wrong result when Python does not raise an error.

Forgetting to subtract ord("a")

If you write counts[ord(ch)] += 1 instead of counts[ord(ch) - ord("a")] += 1, the index is the character's code, not its position in the alphabet. The letter a has code 97, which is past the end of a 26-slot list. The letter z has code 122, and Python raises an error:

The output is:

IndexError: list index out of range

The message does not say which index was bad, so read the line of code: the index is ord(ch), which is the code of the letter, not its slot. The fix is to subtract ord("a") from the character before you use it as an index.

Capital letters in the plain version

The plain count_letters function does not skip capital letters. Calling it with "Listen" does not fail. It counts the capital L in slot 5, the letter f, as the earlier example showed. The count is wrong, and no error tells you so. Lowercase the text first, or use count_letters_safe, which skips anything that is not a lowercase letter.

Reusing one list for two words

Each word needs its own count list. If you reuse one list for a second word without clearing it, the counts add up. Here is a test with two passes over the same two letters:

The output is:

1 1
2 2

The second pass did not start from zero. The fix is to call count_letters again, which makes a new list each time, or to clear the list with reused[:] = [0] * 26 before the second pass.

Comparing lists with is

Python lists compare by content with ==. The comparison count_letters(a) is count_letters(b) asks a different question: whether the two lists are the same object. Two lists made by separate calls are never is each other, even when every slot matches. Use == for every list comparison in this lesson.

Expecting case to be ignored

is_anagram lowercases both words first, but same_counts does not. The call same_counts("Listen", "silent") returns False, because the capital L lands in the wrong slot, and the counts differ from the lowercase word. Choose the function that matches your input. If the input can contain capitals, use the safe version and lowercase first.

Practice

Each exercise has an answer under it. Try each one before you read the answer.

1. Count the letters of hello with count_letters and write down the value in each slot that is not zero. Give the slot number and the letter for each.

Show the answer

The four non-zero slots are: slot 4 is e with 1, slot 7 is h with 1, slot 11 is l with 2, because hello has two l letters, and slot 14 is o with 1. All other slots are 0.

2. Write a function is_pangram(s) that returns True when the text contains every letter from a to z at least once. Use count_letters_safe after lowercasing the text.

Show the answer

def is_pangram(s):
    counts = count_letters_safe(s.lower())
    return all(n > 0 for n in counts)

is_pangram("The quick brown fox jumps over the lazy dog") returns True. is_pangram("The quick brown fox") returns False, because letters such as a, d and z do not appear in that phrase.

3. Write count_singles(word) as shown above, and then predict its result for "mississippi". Check your prediction by running it.

Show the answer

The word mississippi has m once, i four times, s four times and p twice. The only letter that appears exactly once is m, so the function returns 1.

4. The function below is supposed to count letters in a word, but it fails on "zebra". Find the bug and fix it.

def buggy_count(word):
    counts = [0] * 26
    for ch in word:
        counts[ord(ch)] += 1
    return counts

Show the answer

The bug is counts[ord(ch)]. It uses the character's code as the index instead of its position in the alphabet. The fix is counts[ord(ch) - ord("a")] += 1. With that change, "zebra" puts its z in slot 25 and no longer raises an error.

5. Check whether "Schoolmaster" and "The classroom" are anagrams. Predict the answer before you run the code.

Show the answer

They are anagrams. Both phrases contain the same 12 letters once the spaces are skipped and the capitals are made lowercase. The call is_anagram("Schoolmaster", "The classroom") returns True.

Summary

• A character is a number, and ord("a") is 97, so ord(c) - ord("a") gives the position of a lowercase letter from 0 to 25.
• A list of 26 slots holds one count for each letter, and counts[ord(ch) - ord("a")] += 1 adds one to the right slot.
• Compare two count lists with ==, which compares the contents. Use is only for None and object identity.
• A negative index counts from the end of a list, so a capital letter can add to the wrong slot without an error. Skip characters that are not lowercase letters, or lowercase the text first.
• Make a fresh count list for each word, because reusing one list adds the counts together.