Character Frequency Counting in DSA Rust

Mental Model

Count how many times each letter appears in a word or sentence by keeping track in a list or map.

Analogy: Imagine you have a basket of fruits and you want to know how many apples, bananas, and oranges you have. You count each fruit and write down the number next to its name.

Input: "hello"

Frequency Map:
'h' -> 1
'e' -> 1
'l' -> 2
'o' -> 1

Dry Run Walkthrough

Input: string: "hello"

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

Step 1: Read first character 'h' and add it to frequency map with count 1

{'h': 1}

Why: We start counting characters from the beginning

Step 2: Read second character 'e' and add it to frequency map with count 1

{'h': 1, 'e': 1}

Why: Add new character to map with count 1

Step 3: Read third character 'l' and add it to frequency map with count 1

{'h': 1, 'e': 1, 'l': 1}

Why: Add new character to map with count 1

Step 4: Read fourth character 'l' and increase its count to 2

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

Why: Character 'l' already counted, increase count

Step 5: Read fifth character 'o' and add it to frequency map with count 1

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

Why: Add new character to map with count 1

Result:

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

Annotated Code

DSA Rust

use std::collections::HashMap;

fn character_frequency(s: &str) -> HashMap<char, usize> {
    let mut freq_map = HashMap::new();
    for ch in s.chars() {
        *freq_map.entry(ch).or_insert(0) += 1; // increase count or insert 0 then add 1
    }
    freq_map
}

fn main() {
    let input = "hello";
    let freq = character_frequency(input);
    for (ch, count) in freq.iter() {
        println!("'{}' -> {}", ch, count);
    }
}

*freq_map.entry(ch).or_insert(0) += 1;

increase count for character or insert with 0 then add 1

Output

'h' -> 1

'e' -> 1

'l' -> 2

'o' -> 1

Complexity Analysis

Time: O(n) because we look at each character once to count

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

vs Alternative: Using a list or array for fixed character sets can be faster but less flexible; hash map works for any characters

Edge Cases

empty string

returns empty frequency map with no entries

DSA Rust

for ch in s.chars() {

string with all same characters

frequency map has one entry with count equal to string length

DSA Rust

*freq_map.entry(ch).or_insert(0) += 1;

string with special characters and spaces

counts include spaces and special characters as keys

DSA Rust

for ch in s.chars() {

When to Use This Pattern

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

Common Mistakes

Mistake: Forgetting to initialize count to zero before incrementing
Fix: Use or_insert(0) to set initial count before adding 1

Mistake: Using a loop that does not iterate over characters properly
Fix: Use s.chars() to get each character from the string

Summary

Counts how many times each character appears in a string.

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

The key is to update counts in a map as you read each character.

Practice

1. What does character frequency counting mean in simple terms?

easy

A. Counting how many times each character appears in a string

B. Sorting characters alphabetically

C. Replacing characters with numbers

D. Removing duplicate characters from a string

Solution

1. Step 1: Understand the meaning of frequency counting

   Frequency counting means counting how often each item appears.

2. Step 2: Apply to characters in a string

   For characters, it means counting how many times each character shows up in the string.

3. Final Answer:

   Counting how many times each character appears in a string -> Option A

4. Quick Check:

   Frequency counting = Counting occurrences [OK]

Hint: Think: How many times does each letter show up? [OK]

Common Mistakes:

• Confusing frequency counting with sorting
• Thinking frequency means replacing characters
• Mixing frequency with removing duplicates

2. Which Rust code snippet correctly initializes an empty frequency map for characters?

easy

A. let mut freq = std::collections::HashMap::new();

B. let freq = Vec::new();

C. let freq = String::new();

D. let mut freq = 0;

Solution

1. Step 1: Identify the data structure for frequency counting

   Frequency counting needs a map to store character keys and counts as values.

2. Step 2: Check Rust syntax for creating an empty map

   HashMap::new() creates an empty map; mut allows adding entries.

3. Final Answer:

   let mut freq = std::collections::HashMap::new(); -> Option A

4. Quick Check:

   Empty map initialization = HashMap::new() [OK]

Hint: Use HashMap::new() for empty maps in Rust [OK]

Common Mistakes:

• Using Vec or String instead of HashMap
• Not making the map mutable
• Initializing with a number instead of a map

3. What is the output of this Rust code counting characters in "hello"?

use std::collections::HashMap;
fn main() {
    let text = "hello";
    let mut freq = HashMap::new();
    for ch in text.chars() {
        *freq.entry(ch).or_insert(0) += 1;
    }
    println!("{:?}", freq);
}

medium

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

B. {"h": 1, "e": 1, "l": 3, "o": 1}

C. {"h": 1, "e": 1, "l": 2, "o": 1}

D. {"h": 0, "e": 0, "l": 0, "o": 0}

Solution

1. Step 1: Count each character in "hello"

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

2. Step 2: Check code logic for counting

   Code increments count for each character correctly using or_insert(0) and += 1.

3. Final Answer:

   {"h": 1, "e": 1, "l": 2, "o": 1} -> Option C

4. Quick Check:

   Count 'l' twice, others once [OK]

Hint: Count letters carefully, 'l' appears twice in 'hello' [OK]

Common Mistakes:

• Counting 'l' only once
• Confusing keys and values in map
• Assuming zero counts for characters

4. Find the error in this Rust code for counting characters:

use std::collections::HashMap;
fn main() {
    let text = "abcabc";
    let mut freq = HashMap::new();
    for ch in text.chars() {
        freq.insert(ch, freq[&ch] + 1);
    }
    println!("{:?}", freq);
}

medium

A. HashMap is not mutable

B. println! macro is missing semicolon

C. text.chars() is incorrect syntax

D. Using freq[&ch] causes panic if key not present

Solution

1. Step 1: Understand freq[&ch] usage

   freq[&ch] tries to get value for key ch but panics if key missing.

2. Step 2: Identify missing key problem

   On first occurrence, key ch is missing, so freq[&ch] causes runtime panic.

3. Final Answer:

   Using freq[&ch] causes panic if key not present -> Option D

4. Quick Check:

   Accessing missing key with [] panics [OK]

Hint: Use or_insert(0) to avoid missing key panic [OK]

Common Mistakes:

• Assuming freq[&ch] returns 0 if key missing
• Not making HashMap mutable
• Thinking text.chars() is wrong syntax

5. Given a string, how can you count only alphabetic characters ignoring digits and symbols in Rust? Choose the best approach.

hard

A. Count all characters including digits and symbols

B. Use chars().filter(|c| c.is_alphabetic()) and count frequencies

C. Convert string to bytes and count all bytes

D. Replace digits with spaces then count all characters

Solution

1. Step 1: Filter only alphabetic characters

   Use filter with is_alphabetic() to keep letters only.

2. Step 2: Count frequencies on filtered characters

   Count frequencies on filtered chars to ignore digits/symbols.

3. Final Answer:

   Use chars().filter(|c| c.is_alphabetic()) and count frequencies -> Option B

4. Quick Check:

   Filter letters first, then count [OK]

Hint: Filter letters with is_alphabetic() before counting [OK]

Common Mistakes:

• Counting digits and symbols by mistake
• Using bytes which may split characters wrongly
• Replacing digits but forgetting symbols