Character Frequency Counting in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is character frequency counting?

It is the process of counting how many times each character appears in a given string or text.

beginner

Which Rust data structure is commonly used to store character frequencies?

A HashMap is commonly used to map each character to its count.

intermediate

How do you update the count of a character in a Rust HashMap during frequency counting?

Use the entry API with or_insert(0) to get the current count or insert zero, then increment it by one.

intermediate

Why is character frequency counting useful in algorithms?

It helps in problems like anagram detection, compression, and pattern matching by understanding character distribution.

beginner

What is the time complexity of counting character frequencies in a string of length n?

The time complexity is O(n) because each character is processed once.

Which Rust type is best for storing character counts?

A HashMap<char, usize>

B Vec<char>

C String

D Option<char>

HashMap stores each character with its count efficiently.

What does the entry API in Rust HashMap help with during frequency counting?

A Sorting characters

B Converting characters to numbers

C Removing duplicates

D Inserting or updating counts easily

The entry API allows inserting a default value or updating an existing count.

If a string has 100 characters, what is the time complexity to count frequencies?

A O(n)

B O(1)

C O(n^2)

D O(log n)

Counting frequencies requires one pass through the string, so O(n).

Which problem can character frequency counting help solve?

A Finding maximum value

B Sorting numbers

C Anagram detection

D Calculating factorial

Anagram detection uses character counts to compare strings.

What happens if you forget to initialize a character count before incrementing in Rust?

A Compilation error

B Runtime panic

C Count starts at zero automatically

D Count increments from garbage value

Attempting to increment without proper handling (e.g., unwrap on get_mut) causes a runtime panic.

Explain how to count character frequencies in a string using Rust's HashMap.

Think about how to handle characters not seen before.

Describe one real-life use case where character frequency counting is helpful.

Consider comparing two words or compressing text.

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