Cracking the Coding Interview: Is Unique

2023-09-24

• 2 min read

#javascript #algorithms_and_data_structures

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) {
    uniqueChars.add(char);
  }

  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;
}

Resources

Hey! You may like this newsletter if you're enjoying this blog. ❤

✖

Twitter Github