First Non Repeating Character Using Hash in DSA Rust - Execution Trace

Concept Flow - First Non Repeating Character Using Hash

Start with input string

↓

Create empty hash map for counts

↓

For each char in string

↓

Increment count in hash map

↓

For each char in string

↓

Check count in hash map

↓

Return char

↓

If none found, return None

Count characters using a hash map, then find the first character with count 1.

Execution Sample

DSA Rust

fn first_non_repeating_char(s: &str) -> Option<char> {
    let mut counts = std::collections::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
}

This function finds the first character in a string that appears only once using a hash map.

Execution Table

Step	Operation	Character Processed	Hash Map State	Action	Visual State
1	Initialize hash map	-	{}	Create empty map	[]
2	Count char	'a'	{'a':1}	Add 'a' with count 1	[a:1]
3	Count char	'b'	{'a':1, 'b':1}	Add 'b' with count 1	[a:1 -> b:1]
4	Count char	'c'	{'a':1, 'b':1, 'c':1}	Add 'c' with count 1	[a:1 -> b:1 -> c:1]
5	Count char	'a'	{'a':2, 'b':1, 'c':1}	Increment 'a' count to 2	[a:2 -> b:1 -> c:1]
6	Count char	'b'	{'a':2, 'b':2, 'c':1}	Increment 'b' count to 2	[a:2 -> b:2 -> c:1]
7	Count char	'd'	{'a':2, 'b':2, 'c':1, 'd':1}	Add 'd' with count 1	[a:2 -> b:2 -> c:1 -> d:1]
8	Check first non-repeating	'a'	{'a':2, 'b':2, 'c':1, 'd':1}	Count 2, skip	[a:2 -> b:2 -> c:1 -> d:1]
9	Check first non-repeating	'b'	{'a':2, 'b':2, 'c':1, 'd':1}	Count 2, skip	[a:2 -> b:2 -> c:1 -> d:1]
10	Check first non-repeating	'c'	{'a':2, 'b':2, 'c':1, 'd':1}	Count 1, return 'c'	[a:2 -> b:2 -> c:1 -> d:1]
11	Return result	'c'	-	Return Some('c')	[a:2 -> b:2 -> c:1 -> d:1]

💡 Found first character with count 1 at step 10 ('c'), function returns.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 10	Final
counts	{}	{'a':1}	{'a':1, 'b':1}	{'a':1, 'b':1, 'c':1}	{'a':2, 'b':1, 'c':1}	{'a':2, 'b':2, 'c':1}	{'a':2, 'b':2, 'c':1, 'd':1}	{'a':2, 'b':2, 'c':1, 'd':1}	{'a':2, 'b':2, 'c':1, 'd':1}
current_char	-	'a'	'b'	'c'	'a'	'b'	'd'	'c'	'c'
result	None	None	None	None	None	None	None	Some('c')	Some('c')

Key Moments - 3 Insights

Why do we need two loops instead of one?

The first loop counts all characters (see steps 2-7), the second loop finds the first character with count 1 (steps 8-10). Combining both would miss order.

What if the string has no non-repeating characters?

The second loop checks all characters; if none have count 1, the function returns None (not shown in this example but would happen after step 10).

Why do we use a hash map for counting?

The hash map stores counts for each character efficiently, allowing quick lookup during the second loop (see 'counts' variable in variable_tracker).

Visual Quiz - 3 Questions

Look at the execution table, what is the hash map state after processing character 'd'?

A {'a':2, 'b':1, 'c':1, 'd':1}

B {'a':2, 'b':2, 'c':1, 'd':1}

C {'a':1, 'b':1, 'c':1, 'd':1}

D {'a':2, 'b':2, 'c':2, 'd':1}

💡 Hint

Check step 7 in the execution_table for the hash map state after 'd' is processed.

At which step does the function find the first non-repeating character?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look at the 'Action' column in execution_table rows 8-11 to see when the character is returned.

If the input string was "aabbcc", what would the function return?

A None

B Some('c')

C Some('a')

D Some('b')

💡 Hint

Refer to the key_moments about what happens if no character has count 1.

Concept Snapshot

First Non Repeating Character Using Hash

- Use a hash map to count characters.
- First loop: count all characters.
- Second loop: find first char with count 1.
- Return that char or None if none found.
- Maintains order by checking original string again.

Full Transcript

This concept finds the first character in a string that does not repeat. It uses a hash map to count how many times each character appears. First, it loops through the string and counts each character. Then, it loops again to find the first character with count one. If found, it returns that character; otherwise, it returns None. This method keeps the order of characters and efficiently finds the first unique character.

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