Problem
We are given a string and we need to find if the string has unique characters in it.
Examples:
input: dev.to
output: true
input: javascript
output: false
Solution
The solution to this problem is very simple. It involves the usage of the set data structure. We iterate over the string and store the characters of the string in a set. Every time we store a character, we will check if the character already exist in the set. If we find that the character has already been stored in the set, this means that we encountered the character a while back in the string. Thus the string does not have unique characters hands with return false. If we reach till the end of the string and do not find any duplicate occurrences this means that the string is unique and we return true.
bool is_string_unique(string s) {
set<char> store;
for (auto a : s) {
if (store.find(a) != store.end()) {
// charecter already exists
return false;
}
store.insert(a);
}
return true;
}
References: Cracking the Coding Interview - Gayle Laakmann McDowell
Have a nice day 😄
Top comments (3)
Yea, hash maps would work as well. It's just that sets are more suitable as we don't have to store a key-value pair.
Fun fact: Sets are implemented with hash maps!
unordered_setin C++11 uses hash maps behind the scenes.Here's a JavaScript solution. I split the string into a list of characters, and then create a new set from it. A set can only contain unique elements; so if the character list and the set have different lengths, then the original string must have contained duplicated letters.
What a beautiful solution!