Follow

Follow

# Rust Interview Puzzles: Find the first unique character in a string

go4fun.fun
·Jan 25, 2023·

### Problem

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

#### Examples:

 Input `str` Output `"yesterday"` `'s'` `"ifeelfine"` `'l'` `"ob-la-di,ob-la-da"` `'i'` `"help!"` `'h'` `"help!help!"` `None`

### 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