Problem

Given a provided ASCII string str, we need to find the first unique (non-repeating) character.

Examples:

Solution

fn find_first_unique_char(str: &str) -> Option<char> {
    let map = str.chars().fold(HashMap::new(), |mut map, ch| {
        let count = map.entry(ch).or_insert(0u8);
        *count += 1;
        map
    });

    str.chars().find(|c| map.get(c) == Some(&1))
}

Explanation

One simple way to solve the puzzle is to use the auxiliary HashMap and to iterate the input string characters twice. When we iterate it for the first time using fold, we count how many times each character appears in the string, saving counts to the map. When we iterate the string for the second time using find, we just return the first character (wrapped in Some) appearing in the string exactly once. The function find is short-circuiting, so it will stop processing as soon as the first character is found, or otherwise, it will return None.

Complexity

The time complexity of the solution is O(n) (where n is the size of the input string).

The auxiliary space complexity is O(1) even though we used the auxiliary HashMap. That is because a possible set of different characters stored in the map is limited (128 in the case of ASCII characters). It means that there is no linear dependency between the size of the input string and the size of the map.

---

Rust Playground with this code