DEV Community

Sahil Bondre
Sahil Bondre

Posted on

Interview Prep #1: Does String has Unique Characters

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

References: Cracking the Coding Interview - Gayle Laakmann McDowell
Have a nice day 😄

Top comments (3)

Collapse
 
godcrampy profile image
Sahil Bondre

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_set in C++11 uses hash maps behind the scenes.

Collapse
 
witaylor profile image
Will Taylor

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.

const isStringUnique = string => {
    const charList = string.split('');
    const charSet = new Set(charList);

    return charList.length === charSet.size;
}
Collapse
 
godcrampy profile image
Sahil Bondre

What a beautiful solution!