Character Frequency Counting in DSA Rust - Time & Space Complexity

Time Complexity: Character Frequency Counting

O(n)

Understanding Time Complexity

We want to understand how long it takes to count how often each character appears in a string.

How does the time needed grow as the string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

use std::collections::HashMap;

fn char_frequency(s: &str) -> HashMap {
    let mut freq = HashMap::new();
    for ch in s.chars() {
        *freq.entry(ch).or_insert(0) += 1;
    }
    freq
}
    

This code counts how many times each character appears in the input string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the string once.
• How many times: Exactly once for each character, so as many times as the string length.

How Execution Grows With Input

As the string gets longer, the number of steps grows directly with the number of characters.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows in a straight line with input size; doubling input doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to count characters grows directly with the string length.

Common Mistake

[X] Wrong: "Counting characters takes longer because of the hash map operations inside the loop."

[OK] Correct: Each hash map insertion or update is on average constant time, so it does not add extra growth beyond the loop over characters.

Interview Connect

Knowing how to analyze simple loops with hash maps helps you explain efficient counting and lookup tasks clearly in interviews.

Self-Check

"What if we used a sorted array instead of a hash map to store counts? How would the time complexity change?"

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