Character Frequency Counting in DSA Rust - Execution Trace

Concept Flow - Character Frequency Counting

Start with empty frequency map

↓

Read next character from string

↓

Is character in map?

No→Add character with count 1

|Yes↓

Increment character count by 1

↓

More characters?

Yes→Read next character

No↓

Done: frequency map ready

We start with an empty map, read each character, add or update its count, and finish when all characters are processed.

Execution Sample

DSA Rust

use std::collections::HashMap;

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

Counts how many times each character appears in the string "hello".

Execution Table

Step	Operation	Character	Frequency Map State	Visual State
1	Start	-	{}	{}
2	Read character	h	{}	{}
3	Add 'h' with count 1	h	{"h":1}	{"h":1}
4	Read character	e	{"h":1}	{"h":1}
5	Add 'e' with count 1	e	{"h":1, "e":1}	{"h":1, "e":1}
6	Read character	l	{"h":1, "e":1}	{"h":1, "e":1}
7	Add 'l' with count 1	l	{"h":1, "e":1, "l":1}	{"h":1, "e":1, "l":1}
8	Read character	l	{"h":1, "e":1, "l":1}	{"h":1, "e":1, "l":1}
9	Increment 'l' count to 2	l	{"h":1, "e":1, "l":2}	{"h":1, "e":1, "l":2}
10	Read character	o	{"h":1, "e":1, "l":2}	{"h":1, "e":1, "l":2}
11	Add 'o' with count 1	o	{"h":1, "e":1, "l":2, "o":1}	{"h":1, "e":1, "l":2, "o":1}
12	No more characters	-	{"h":1, "e":1, "l":2, "o":1}	{"h":1, "e":1, "l":2, "o":1}

💡 All characters processed, frequency map complete.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
freq	{}	{"h":1}	{"h":1, "e":1}	{"h":1, "e":1, "l":1}	{"h":1, "e":1, "l":2}	{"h":1, "e":1, "l":2, "o":1}	{"h":1, "e":1, "l":2, "o":1}
ch	-	h	e	l	l	o	-

Key Moments - 3 Insights

Why do we add a character with count 1 instead of 0 when it's first seen?

Because the first time we see a character, it has appeared once. The execution_table row 3 shows adding 'h' with count 1 immediately after reading it.

Why do we increment the count instead of adding a new entry when the character repeats?

Because the character already exists in the map, so we increase its count. See execution_table rows 8 and 9 where 'l' count goes from 1 to 2.

What happens if the input string is empty?

The loop never runs, so the frequency map stays empty as shown in execution_table row 1 and 12 with no changes.

Visual Quiz - 3 Questions

Look at the execution_table, what is the frequency map after step 7?

A {"h":1, "e":1}

B {"h":1, "e":1, "l":1}

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

D {}

💡 Hint

Check the Frequency Map State column at step 7 in the execution_table.

At which step does the character 'l' count increase from 1 to 2?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look at the Operation and Frequency Map State columns around steps 8 and 9.

If the input string was "aaa", how would the frequency map look after processing all characters?

A {"a":3}

B {"a":1}

C {"a":2}

D {}

💡 Hint

Consider how the count increments each time the same character appears, as shown in variable_tracker for 'l'.

Concept Snapshot

Character Frequency Counting:
- Use a map to track counts
- For each character:
  - If new, add with count 1
  - If existing, increment count
- Result: map with characters and their frequencies

Full Transcript

This visualization shows how to count character frequencies in a string using a map. We start with an empty map. For each character read, if it is not in the map, we add it with count 1. If it is already there, we increase its count by 1. This continues until all characters are processed. The final map shows how many times each character appeared. For example, in the string "hello", 'h', 'e', and 'o' appear once, while 'l' appears twice. If the string is empty, the map remains empty.

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