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.

Practice

1. What does character frequency counting help us find in a string?

easy

A. How many times each character appears

B. The length of the string

C. The first character in the string

D. The position of the last character

Solution

1. Step 1: Understand the purpose of frequency counting

   Frequency counting means counting how many times each character appears in a string.

2. Step 2: Compare options with the definition

   Only How many times each character appears matches the purpose of character frequency counting.

3. Final Answer:

   How many times each character appears -> Option A

4. Quick Check:

   Frequency counting = count characters [OK]

Hint: Frequency counting means counting characters [OK]

Common Mistakes:

• Confusing frequency with string length
• Thinking it finds character positions
• Mixing frequency with sorting

2. Which of the following Python code snippets correctly counts character frequency in string s?

easy

A. freq = 0; for ch in s: freq += 1

B. freq = []; for ch in s: freq.append(ch)

C. freq = {}; for ch in s: freq[ch] = freq.get(ch, 0) + 1

D. freq = {}; for ch in s: freq[ch] = 1

Solution

1. Step 1: Analyze each code snippet

   freq = {}; for ch in s: freq[ch] = freq.get(ch, 0) + 1 uses a dictionary and increments count for each character correctly. freq = []; for ch in s: freq.append(ch) just collects characters in a list. freq = 0; for ch in s: freq += 1 counts total characters, not frequency per character. freq = {}; for ch in s: freq[ch] = 1 sets frequency to 1 always, ignoring repeats.

2. Step 2: Confirm correct frequency counting logic

   Only freq = {}; for ch in s: freq[ch] = freq.get(ch, 0) + 1 correctly counts how many times each character appears.

3. Final Answer:

   freq = {}; for ch in s: freq[ch] = freq.get(ch, 0) + 1 -> Option C

4. Quick Check:

   Use dict with get() to count [OK]

Hint: Use dict with get() to count frequencies [OK]

Common Mistakes:

• Using list instead of dict for counting
• Overwriting counts instead of incrementing
• Counting total length instead of per character

3. What is the output of this code?

text = 'hello'
freq = {}
for ch in text:
    freq[ch] = freq.get(ch, 0) + 1
print(freq)

medium

A. {'h': 1, 'e': 1, 'l': 1, 'o': 1}

B. {'h': 1, 'e': 1, 'l': 2, 'o': 1}

C. {'h': 1, 'e': 1, 'l': 3, 'o': 1}

D. {'h': 1, 'e': 1, 'l': 2}

Solution

1. Step 1: Count characters in 'hello'

   Characters: h(1), e(1), l(2), o(1)

2. Step 2: Check code logic

   Code correctly counts each character's frequency using dict and get().

3. Final Answer:

   {'h': 1, 'e': 1, 'l': 2, 'o': 1} -> Option B

4. Quick Check:

   Count 'l' twice, others once [OK]

Hint: Count repeated letters carefully [OK]

Common Mistakes:

• Counting 'l' only once
• Missing last character
• Incorrect dictionary format

4. Find the error in this code that counts character frequency:

text = 'apple'
freq = {}
for ch in text:
    freq[ch] += 1
print(freq)

medium

A. freq[ch] is used before initialization

B. Loop variable name is wrong

C. print statement syntax error

D. String 'apple' is invalid

Solution

1. Step 1: Identify how freq[ch] is updated

   freq[ch] += 1 tries to add 1 to freq[ch] without initializing freq[ch] first.

2. Step 2: Understand dictionary key initialization

   Since freq is empty initially, freq[ch] does not exist and causes an error.

3. Final Answer:

   freq[ch] is used before initialization -> Option A

4. Quick Check:

   Initialize dict keys before incrementing [OK]

Hint: Initialize dict keys before incrementing [OK]

Common Mistakes:

• Assuming dict keys auto-initialize
• Ignoring error messages
• Changing loop variable unnecessarily

5. Given a string s = 'banana', which code snippet correctly returns a dictionary with only characters that appear more than once?

hard

A. freq = {ch: 1 for ch in s if s.count(ch) > 1}

B. freq = {ch: s.count(ch) for ch in s}

C. freq = {ch for ch in s if s.count(ch) > 1}

D. freq = {ch: s.count(ch) for ch in set(s) if s.count(ch) > 1}

Solution

1. Step 1: Understand the goal

   We want a dictionary with characters appearing more than once and their counts.

2. Step 2: Analyze each option

   freq = {ch: 1 for ch in s if s.count(ch) > 1} sets count to 1 always, ignoring actual counts. freq = {ch: s.count(ch) for ch in set(s) if s.count(ch) > 1} uses set(s) to avoid duplicates and filters counts > 1 correctly. freq = {ch for ch in s if s.count(ch) > 1} creates a set instead of dictionary with counts. freq = {ch: s.count(ch) for ch in s} includes all characters regardless of count.

3. Final Answer:

   freq = {ch: s.count(ch) for ch in set(s) if s.count(ch) > 1} -> Option D

4. Quick Check:

   Use set to avoid duplicates and filter counts [OK]

Hint: Use set(s) and filter counts > 1 [OK]

Common Mistakes:

• Not using set to avoid duplicate keys
• Assigning wrong counts
• Including characters with single occurrence