TK
Home

# Cracking the Coding Interview: Is Unique

Photo by wuz

This post is part of the `Algorithms Problem Solving` series and a problem from the Cracking the Coding Interview book.

## Problem description

Is Unique: Implement an algorithm to determine if a string has all unique characters.

## Examples

``````input: 'asdfghjkl'
output: true

input: 'asdfghjkla'
output: false
``````

## Solutions

Comparing each character with all the other characters. If there's a matching, it's not a string with unique characters

• Runtime Complexity: O(N^2)
• Space Complexity: O(1)
``````function isUnique(string) {
for (let i = 0; i < string.length; i++) {
for (let j = i + 1; j < string.length; j++) {
if (string[i] === string[j]) return false;
}
}

return true;
}
``````

Sorting the string characters and comparing characters two by two.

• Runtime Complexity: O(NlogN) because of the sorting runtime complexity
• Space Complexity: O(N) because of the newly created array
``````function isUnique(string) {
let sortedString = [...string].sort(
(a, b) => a.charCodeAt() - b.charCodeAt()
);

for (let index = 0; index < sortedString.length - 1; index++) {
if (sortedString[index] === sortedString[index + 1]) return false;
}

return true;
}
``````

Using a hashmap to count the number of characters in the string If there's already a character, it should return false as a result If it passes the entire string, it means it's a string with unique characters

• Time Complexity: O(N), N = number of charactes in the string
• Space Complexity: O(N), N = number of charactes in the string stored in the `charMap` hashmap
``````function isUnique(string) {
const charMap = new Map();

for (let char of string) {
if (charMap.has(char)) return false;
charMap.set(char, 1);
}

return true;
}
``````

Using a set to store all unique characters of the string If the size of the set is equal to the string, the string has unique characters

• Time Complexity: O(N), N = number of charactes in the string
• Space Complexity: O(N), N = number of charactes in the string stored in the `uniqueChars` set
``````function isUniqueWithSet(string) {
const uniqueChars = new Set();

for (let char of string) {
}

return uniqueChars.size === string.length;
}
``````

Using a set to store all unique characters of the string A simplified version using the Set constructor

• Time Complexity: O(N), N = number of charactes in the string
• Space Complexity: O(N), N = number of charactes in the string stored in the `uniqueChars` set
``````function isUniqueWithSetSimplified(string) {
return string.length === new Set(string).size;
}
``````