lesson 54 String Algorithms · intermediate

Count characters and words

count() tells how many times a value appears in a text or a list. Counting each distinct value gives a frequency table; comparing counts tells whether two words are anagrams; counting runs compresses text.

You'll be able to

Use count on a text and on a list, and know it counts non-overlapping matches
Build a frequency list: each distinct value once, with its count
Decide whether two texts are anagrams by comparing the count of every letter

The idea

Counting answers a surprising number of text questions: *how many complaints mention a fee?*, *which word appears most?*, *are these two words made of the same letters?* text.count(piece) counts how many times piece occurs in a text, and items.count(value) counts a value in a list.

A frequency table is a count for each distinct value. Walk the values, skip any you have already counted, and pair each new one with its count.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Letters in a word, words in a review

word = "mississippi"
print(word.count("s"), word.count("ss"), word.count("issi"))
letters = []
for ch in word:
    if ch not in letters:
        letters.append(ch)
for ch in letters:
    print(ch, word.count(ch))
words = "great fit great price poor box".split()
print(words.count("great"), words.count("box"), words.count("gr"))

Two words are anagrams when they use exactly the same letters the same number of times: *listen* and *silent*. Comparing counts says that directly: for every letter in either word, the counts must match. (Sorting both words' letters and comparing the lists works too, and is shorter; counting is the idea that later scales to whole documents.)

Counting runs of the same character in a row is a different job: walk the text and keep a count that resets whenever the character changes. That is the idea behind run-length encoding, a simple compression.

example-2.py · Anagrams by counting, and runs of a character

def is_anagram(a, b):
    """Return True if a and b use the same letters the same number of times (case and spaces ignored)."""
    a = a.lower().replace(" ", "")
    b = b.lower().replace(" ", "")
    for ch in a + b:
        if a.count(ch) != b.count(ch):
            return False
    return True

def longest_run(text):
    """Return (character, length) of the longest run of one character, or None for empty text."""
    if text == "":
        return None
    best_ch = text[0]
    best_len = 0
    run_len = 0
    for i in range(len(text)):
        if i > 0 and text[i] == text[i - 1]:
            run_len = run_len + 1
        else:
            run_len = 1
        if run_len > best_len:
            best_ch = text[i]
            best_len = run_len
    return best_ch, best_len

print(is_anagram("Listen", "Silent"), is_anagram("Dormitory", "dirty room"), is_anagram("aab", "abb"))
print(longest_run("WWWBWWWWBB"), longest_run(""))

When to use it: keyword frequency, letter statistics, anagram and permutation checks, simple compression. Mistakes to avoid:

Counting the same value again for every repeat: build the list of distinct values first.
Expecting count to find overlapping matches.
Counting words in raw text: normalise and split first, or "fee" will also be counted inside "feedback".

This lesson calls count once per distinct value, which rescans the text each time. The Collection Algorithms module shows how to count everything in a single pass with a dictionary.

Review

count counts non-overlapping occurrences in a text, or equal items in a list.
A frequency table pairs each distinct value with its count; anagrams have equal counts for every letter of both words.
Runs need a counter that resets when the character changes.
Next: check what a text is made of with isdigit, isalpha and isalnum.

Practise this