Iterating Over Strings
A string might contain letters, digits, punctuation, or Unicode symbols.
Counting What Appears
Suppose you need to analyze a word and determine how often each character appears. For the word brontosaurus, the letters r, o, s, and u each appear twice, while b, n, t, and a appear once. This kind of frequency count records how often each item occurs.
A histogram is a collection of counters. In character counting, the dictionary containing each character and its frequency is the histogram, even when no graph is drawn.
The counting problem has three common strategies: use separate variables, use a list, or use a dictionary. All three can represent frequencies, but they differ in how much information must be known before processing begins and how much storage is reserved.
Three Storage Strategies
| Approach | How counts are stored | Main limitation |
|---|---|---|
| Separate variables | One variable for each possible character | The possible characters must be decided in advance |
| List | A fixed position represents each possible character | The possible character range and its numeric codes must be known |
| Dictionary | A key represents a character and its value stores the count | The dictionary must be updated as characters are encountered |
The three character-counting approaches differ mainly in whether they require a predefined character set.
Separate variables and a fixed-size list require planning. For example, using 26 variables or a 26-element list reserves room for every letter of the alphabet, whether or not every letter appears. The list approach can work when the input is restricted to English letters and characters are converted to indices with ord(), but it depends on that known range.
A dictionary takes a different approach. It creates an entry only when a character actually appears. This means the dictionary does not require you to decide in advance exactly which characters the input will contain.
The Dictionary Decision
The dictionary algorithm uses one decision for every character. If the character is not already a key in the dictionary, add it with a count of 1. If it is already present, increase its existing count by 1. The pattern is if c not in d: initialize; otherwise: increment.
text = "brontosaurus"
d = {}
for c in text:
if c not in d:
d[c] = 1
else:
d[c] = d[c] + 1
print(d)- 1The empty dictionary has no keys before the loop begins.
- 2For each character c, the condition checks whether c is already a key in d.
- 3When c is new, d[c] = 1 creates its first counter.
- 4When c is already present, d[c] = d[c] + 1 updates the existing counter.
- 5After the loop, each key-value pair records a character and its frequency.
- text supplies the characters to process.
- d begins as an empty dictionary.
- The loop processes one character at a time.
- A new character receives the count 1.
- A previously observed character has its count increased.
{'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}Tracing Each Character
The word brontosaurus contains 12 characters but only 8 unique letters. The dictionary changes whenever the loop reads a character for the first time, and it changes an existing value whenever a repeated character is encountered.
| Step | Character read | Dictionary after the step |
|---|---|---|
| 1 | b | {'b': 1} |
| 2 | r | {'b': 1, 'r': 1} |
| 3 | o | {'b': 1, 'r': 1, 'o': 1} |
| 4 | n | {'b': 1, 'r': 1, 'o': 1, 'n': 1} |
| 5 | t | {'b': 1, 'r': 1, 'o': 1, 'n': 1, 't': 1} |
| 6 | o | {'b': 1, 'r': 1, 'o': 2, 'n': 1, 't': 1} |
| 7 | s | {'b': 1, 'r': 1, 'o': 2, 'n': 1, 't': 1, 's': 1} |
| 8 | a | {'b': 1, 'r': 1, 'o': 2, 'n': 1, 't': 1, 's': 1, 'a': 1} |
| 9 | u | {'b': 1, 'r': 1, 'o': 2, 'n': 1, 't': 1, 's': 1, 'a': 1, 'u': 1} |
| 10 | r | {'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 1, 'a': 1, 'u': 1} |
| 11 | u | {'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 1, 'a': 1, 'u': 2} |
| 12 | s | {'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2} |
Each new character creates a key with value 1; each repeated character increases an existing value.
Why Dictionaries Adapt
The dictionary approach is useful when the possible input is not known ahead of time. A string might contain letters, digits, punctuation, or Unicode symbols. A fixed list would require you to know the full range of possible characters and their numeric codes, while a dictionary can create keys for the characters that actually arrive.
The same check-and-update pattern also extends beyond characters. The source describes the pattern as useful for frequency tables, tallies, and histograms, and notes that it can be adapted to counting words or analyzing text in multiple languages.
Choose a dictionary when the input character set may vary, when only characters that appear should receive entries, or when you want the same counting pattern to transfer to other kinds of frequency data.
Common Counting Mistakes
Common mistake Incrementing a dictionary key before creating it.
What it looks likeTrying to increase d[c] immediately when c has not appeared before.
Why it failsA new character does not yet have a counter in the dictionary.
Do this insteadCheck whether c is in d. Create d[c] with value 1 when it is new; otherwise increment the existing value.
Common mistake Treating every character as a repeated character.
What it looks likeUsing only the increment branch for every character.
Why it failsThe first occurrence of a character needs initialization rather than an update.
Do this insteadUse the if c not in d decision to distinguish first occurrences from later occurrences.
Common mistake Choosing a fixed list without considering the input.
What it looks likeUsing a 26-element list for input that may contain digits, punctuation, or Unicode symbols.
Why it failsThe list approach requires the possible character range and numeric codes to be known.
Do this insteadUse a dictionary when the input can contain characters outside a known fixed range.
Common mistake Assuming the dictionary must contain every possible character.
What it looks likeExpecting entries for alphabet letters that never occur in the input.
Why it failsThe dictionary approach creates entries only for characters that actually appear.
Do this insteadInterpret the dictionary as a record of observed characters and their frequencies.
Practice the Trace
What do you think happens?
What will the dictionary contain after this loop processes the string "abaca"?
Reveal answer
{'a': 3, 'b': 1, 'c': 1}
The first a creates a count of 1, b creates a count of 1, the second a increases a to 2, c creates a count of 1, and the final a increases a to 3.
Trace the string "level" one character at a time. Write the dictionary after each character is processed, then identify which keys have a final count greater than 1.
Hints
- Begin with an empty dictionary.
- Create a key with value 1 the first time a character appears.
- Increase the value when the character appears again.
Key Takeaways
- 1Character frequencies can be stored with separate variables, a list, or a dictionary.
- 2Variables and fixed lists require the possible character set to be decided in advance.
- 3The dictionary pattern checks whether a character is already present, then initializes or increments its count.
- 4A dictionary stores only characters that actually appear, so it adapts to letters, digits, punctuation, and Unicode symbols.
- 5The dictionary is a histogram: its keys are the observed items and its values are their frequencies.
At a glance
- A frequency counter records how often each character appears.
- The key dictionary decision is whether the current character is new or already present.
- New characters receive a count of 1, while repeated characters increase their existing count.
- Dictionaries are usually the most adaptable choice because they store only observed characters and do not require a predefined character range.