First Non Repeating Character Using Hash in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new empty hash map.

DSA Rust

let mut counts = std::collections::HashMap::[1]();

Drag options to blanks, or click blank then click option'

Aremove

Binsert

Cget

Dnew

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert instead of new to create the map.

Trying to get or remove before the map exists.

We use HashMap::new() to create an empty hash map to store character counts.

2fill in blank

medium

Complete the code to increase the count of a character in the hash map.

DSA Rust

let count = counts.entry(ch).or_insert(0);
*count [1] 1;

Drag options to blanks, or click blank then click option'

A*=

B-=

C+=

D/=

Attempts:

3 left

💡 Hint

Common Mistakes

Using -= which decreases the count.

Using * or / which are not for addition.

We add 1 to the current count to track how many times the character appears.

3fill in blank

hard

Fix the error in the code to find the first non-repeating character.

DSA Rust

for ch in s.chars() {
    if counts.get(&ch) == Some(&[1]) {
        return Some(ch);
    }
}

Drag options to blanks, or click blank then click option'

ANone

B1

C2

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 which means character not present.

Checking for 2 or None which are incorrect.

We check if the count is 1 to find the first character that appears only once.

4fill in blank

hard

Fill both blanks to complete the function that returns the first non-repeating character or None.

DSA Rust

fn first_non_repeating(s: &str) -> Option<char> {
    let mut counts = std::collections::HashMap::[1]();
    for ch in s.chars() {
        let count = counts.entry(ch).or_insert(0);
        *count [2] 1;
    }
    for ch in s.chars() {
        if counts.get(&ch) == Some(&1) {
            return Some(ch);
        }
    }
    None
}

Drag options to blanks, or click blank then click option'

Anew

B+=

C-=

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert instead of new to create the map.

Using -= instead of += to update counts.

We create a new hash map and add 1 to counts for each character.

5fill in blank

hard

Fill all three blanks to complete the main function that tests the first_non_repeating function.

DSA Rust

fn main() {
    let s = "[1]";
    match first_non_repeating(s) {
        Some(ch) => println!("First non-repeating character: {}", [2]),
        None => println!("No non-repeating character found."),
    }
    // Output should be: [3]
}

Drag options to blanks, or click blank then click option'

Ahello

Bch

Ch

Dworld

Attempts:

3 left

💡 Hint

Common Mistakes

Using a string with no non-repeating characters.

Printing the wrong variable or output.

We test with string "hello", print the found character ch, which should be 'h'.

Practice

1. What is the main purpose of using a hash map when finding the first non-repeating character in a string?

easy

A. To sort the characters alphabetically

B. To store the frequency of each character for quick lookup

C. To reverse the string efficiently

D. To convert characters to uppercase

Solution

1. Step 1: Understand the role of hash map

   A hash map stores each character as a key and its count as the value, allowing quick frequency lookup.

2. Step 2: Why frequency matters

   Knowing frequency helps identify which character appears only once, the first non-repeating character.

3. Final Answer:

   To store the frequency of each character for quick lookup -> Option B

4. Quick Check:

   Hash map = frequency storage [OK]

Hint: Use hash map to count characters fast [OK]

Common Mistakes:

• Thinking hash map sorts characters
• Using hash map to reverse string
• Ignoring frequency counts

2. Which Rust data structure is best suited to implement the frequency count for characters in a string?

easy

A. HashMap

B. Vec<char>

C. String

D. Option<char>

Solution

1. Step 1: Identify data structure for key-value pairs

   HashMap stores characters as keys and their counts as values, perfect for frequency counting.

2. Step 2: Why others don't fit

   Vec<char> is just a list, String holds characters but no counts, Option<char> holds one optional char only.

3. Final Answer:

   HashMap -> Option A

4. Quick Check:

   HashMap = char to count map [OK]

Hint: Use HashMap for frequency counts [OK]

Common Mistakes:

• Using Vec instead of HashMap
• Confusing String with frequency map
• Using Option for multiple counts

3. What will be the output of the following Rust code snippet?

use std::collections::HashMap;

fn first_non_repeating(s: &str) -> Option<char> {
    let mut counts = HashMap::new();
    for c in s.chars() {
        *counts.entry(c).or_insert(0) += 1;
    }
    for c in s.chars() {
        if counts[&c] == 1 {
            return Some(c);
        }
    }
    None
}

fn main() {
    let result = first_non_repeating("swiss");
    println!("{:?}", result);
}

medium

A. Some('s')

B. None

C. Some('i')

D. Some('w')

Solution

1. Step 1: Count character frequencies in "swiss"

   's' appears 3 times, 'w' once, 'i' once.

2. Step 2: Find first character with count 1 in original order

   Order: 's'(3), 'w'(1), 'i'(1), 's'(3), 's'(3). First with count 1 is 'w'.

3. Final Answer:

   Some('w') -> Option D

4. Quick Check:

   First unique char = 'w' [OK]

Hint: Check counts then first unique char in order [OK]

Common Mistakes:

• Picking first char without checking count
• Confusing 'i' and 'w' positions
• Ignoring multiple occurrences

4. Identify the bug in this Rust function to find the first non-repeating character:

fn first_non_repeating(s: &str) -> Option<char> {
    let mut counts = std::collections::HashMap::new();
    for c in s.chars() {
        counts.insert(c, 1);
    }
    for c in s.chars() {
        if counts[&c] == 1 {
            return Some(c);
        }
    }
    None
}

medium

A. Using insert overwrites counts, so frequencies are incorrect

B. Missing return type Option<char>

C. Using s.chars() instead of s.bytes()

D. No bug, code works correctly

Solution

1. Step 1: Analyze frequency counting loop

   Using counts.insert(c, 1) overwrites previous counts, so frequency is always 1.

2. Step 2: Effect on result

   All characters appear counted as 1, so function returns first char incorrectly.

3. Final Answer:

   Using insert overwrites counts, so frequencies are incorrect -> Option A

4. Quick Check:

   insert overwrites count, use entry().or_insert() [OK]

Hint: Use entry().or_insert() to update counts [OK]

Common Mistakes:

• Using insert instead of entry().or_insert()
• Ignoring frequency updates
• Confusing chars and bytes

5. Given a string that may contain Unicode characters, how would you modify the Rust function to correctly find the first non-repeating character considering Unicode graphemes instead of chars? Choose the best approach.

hard

A. Use chars() iterator as usual, it handles graphemes correctly

B. Convert string to bytes and count byte frequencies

C. Use the unicode-segmentation crate to iterate over graphemes and count frequencies

D. Replace all Unicode characters with ASCII equivalents before counting

Solution

1. Step 1: Understand Unicode graphemes vs chars

   Rust's chars() iterates Unicode scalar values, not grapheme clusters (user-perceived characters).

2. Step 2: Use unicode-segmentation crate

   This crate provides graphemes() iterator to correctly handle combined Unicode characters.

3. Step 3: Count frequencies using graphemes

   Counting graphemes ensures correct identification of non-repeating user-visible characters.

4. Final Answer:

   Use the unicode-segmentation crate to iterate over graphemes and count frequencies -> Option C

5. Quick Check:

   Unicode graphemes need special iterator [OK]

Hint: Use unicode-segmentation crate for grapheme counting [OK]

Common Mistakes:

• Assuming chars() equals graphemes
• Counting bytes instead of characters
• Replacing Unicode with ASCII loses data