Character Frequency Counting in DSA Python

Mental Model

Count how many times each letter appears in a word or sentence by keeping track as you look at each letter once.

Analogy: Imagine sorting colored beads into jars by color, putting one bead in the right jar each time you see it.

word: h -> e -> l -> l -> o -> null
freq: {}
↑ current letter

Dry Run Walkthrough

Input: string: "hello"

Goal: Find how many times each character appears in the string

Step 1: Look at first letter 'h' and add it to frequency map with count 1

freq: { 'h': 1 }
word: h -> e -> l -> l -> o -> null
↑ at 'h'

Why: We start counting the first letter

Step 2: Look at second letter 'e' and add it to frequency map with count 1

freq: { 'h': 1, 'e': 1 }
word: h -> e -> l -> l -> o -> null
↑ at 'e'

Why: Add new letter to frequency map

Step 3: Look at third letter 'l' and add it to frequency map with count 1

freq: { 'h': 1, 'e': 1, 'l': 1 }
word: h -> e -> l -> l -> o -> null
↑ at first 'l'

Why: Add new letter to frequency map

Step 4: Look at fourth letter 'l' and increase its count to 2

freq: { 'h': 1, 'e': 1, 'l': 2 }
word: h -> e -> l -> l -> o -> null
↑ at second 'l'

Why: Letter 'l' seen again, increase count

Step 5: Look at fifth letter 'o' and add it to frequency map with count 1

freq: { 'h': 1, 'e': 1, 'l': 2, 'o': 1 }
word: h -> e -> l -> l -> o -> null
↑ at 'o'

Why: Add new letter to frequency map

Result:

freq: { 'h': 1, 'e': 1, 'l': 2, 'o': 1 }

Annotated Code

DSA Python

def char_frequency(s: str) -> dict:
    freq = {}
    for ch in s:
        if ch in freq:
            freq[ch] += 1  # increase count for existing character
        else:
            freq[ch] = 1   # add new character with count 1
    return freq

# Driver code
input_str = "hello"
result = char_frequency(input_str)
for ch, count in result.items():
    print(f"'{ch}': {count}")

for ch in s:

iterate over each character in the string

if ch in freq:

check if character already counted

freq[ch] += 1 # increase count for existing character

increment count for repeated character

freq[ch] = 1 # add new character with count 1

initialize count for new character

Output

'h': 1

'e': 1

'l': 2

'o': 1

Complexity Analysis

Time: O(n) because we look at each character once in the string of length n

Space: O(k) where k is number of unique characters, because we store counts for each unique character

vs Alternative: Using nested loops to count each character repeatedly would be O(n^2), so this method is much faster

Edge Cases

empty string

returns empty frequency map

DSA Python

for ch in s:

string with all same characters, e.g. "aaa"

returns frequency map with one character count equal to string length

DSA Python

freq[ch] += 1  # increase count for existing character

string with spaces and punctuation, e.g. "hi! hi!"

counts spaces and punctuation as characters

DSA Python

if ch in freq:

When to Use This Pattern

When you need to count how many times each item appears in a collection, use character frequency counting to track counts efficiently.

Common Mistakes

Mistake: Forgetting to initialize count to 1 for new characters
Fix: Add else clause to set freq[ch] = 1 when character is first seen

Mistake: Using nested loops to count each character separately
Fix: Use a single pass with a dictionary to count frequencies in one loop

Summary

Counts how many times each character appears in a string.

Use when you want to know the frequency of letters or symbols in text.

The key is to update counts as you see each character once.