First Non Repeating Character Using Hash in DSA Rust

Mental Model

We want to find the first character in a string that appears only once by counting how many times each character shows up.

Analogy: Imagine a line of people where some people appear multiple times. We want to find the first person who is standing alone without any twins behind or ahead.

string: h -> e -> l -> l -> o -> null
hash: {h:1, e:1, l:2, o:1}
↑ first unique char pointer

Dry Run Walkthrough

Input: string: "hello"

Goal: Find the first character that appears only once in the string

Step 1: Count characters: see 'h', add or update count

hash: {h:1}

Why: We need to know how many times each character appears

Step 2: Count characters: see 'e', add or update count

hash: {h:1, e:1}

Why: Keep counting all characters

Step 3: Count characters: see 'l', add or update count

hash: {h:1, e:1, l:1}

Why: Count 'l' for the first time

Step 4: Count characters: see second 'l', update count

hash: {h:1, e:1, l:2}

Why: Update count because 'l' appears again

Step 5: Count characters: see 'o', add or update count

hash: {h:1, e:1, l:2, o:1}

Why: Count 'o' for the first time

Step 6: Scan string from start to find first char with count 1

string: h -> e -> l -> l -> o -> null
counts: h=1, e=1, l=2, o=1

Why: We want the first unique character in order

Step 7: Check 'h' count=1, return 'h' as first non repeating

result: 'h'

Why: 'h' is the first character that appears only once

Result:

h

Annotated Code

DSA Rust

use std::collections::HashMap;

fn first_non_repeating_char(s: &str) -> Option<char> {
    let mut counts = HashMap::new();
    // Count each character's frequency
    for ch in s.chars() {
        *counts.entry(ch).or_insert(0) += 1;
    }
    // Find first character with count 1
    for ch in s.chars() {
        if let Some(&1) = counts.get(&ch) {
            return Some(ch);
        }
    }
    None
}

fn main() {
    let input = "hello";
    match first_non_repeating_char(input) {
        Some(ch) => println!("{}", ch),
        None => println!("No unique character found"),
    }
}

*counts.entry(ch).or_insert(0) += 1;

increment count for each character to track frequency

for ch in s.chars() {

iterate characters in original order to find first unique

if let Some(&1) = counts.get(&ch) {

check if character count is exactly one

return Some(ch);

return the first non repeating character found

Output

h

Complexity Analysis

Time: O(n) because we scan the string twice: once to count and once to find the first unique character

Space: O(k) where k is the number of unique characters stored in the hash map

vs Alternative: Compared to checking each character by scanning the whole string repeatedly (O(n^2)), using a hash map is much faster and efficient

Edge Cases

empty string

returns None because there are no characters

DSA Rust

None

all characters repeating

returns None because no unique character exists

DSA Rust

None

string with one character

returns that character as it is unique

DSA Rust

return Some(ch);

When to Use This Pattern

When you need to find the first unique element in a sequence, use a hash map to count frequencies and then scan in order to find the first with count one.

Common Mistakes

Mistake: Checking counts while counting characters instead of after counting all
Fix: First count all characters, then scan again to find the first unique

Mistake: Using a data structure that does not preserve order
Fix: Scan the original string again in order to preserve character order

Summary

Finds the first character in a string that appears only once using a hash map to count frequencies.

Use when you need to identify the earliest unique character efficiently.

Count all characters first, then scan in order to find the first with count one.

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