Rust Interview Puzzles: Find the first unique character in a string
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.