Is Unique - Online Learning Platform

Data structures and Algorithms in Javascript

About Lesson

We will address the following Topics

Question

Design an algorithm to check if a string contains only distinct characters. If you’re restricted from using extra data structures, how would you approach this problem?

Explanation

The question is asking you to create an algorithm to determine whether a given string contains all unique characters. In other words, you need to check if there are no duplicate characters within the string.

Examples

Example 1:

Input: "abcdefg"
Output: true
Explanation: returns true because all characters are unique.

Example 2:

Input: "hello"
Output: false
Explanation: returns false because ‘l’ appears twice.

Constraints

Character set is ASCII

Practice

dummy

Hint

Store each character in a map and verify if the following character is present in the map.
This process ensures a time complexity of O(N) when the character length exceeds 128, with a space complexity of O(1)

/** * check if a string contains only distinct characters * @param {string} str * @return {boolean} */ const isUniqueChars = (str) => { }; // **** some Tests from here **** const assert = require("assert") // Test 1: Given a string with chars greater than 128, it should return false const test1Result = isUniqueChars('qwertyuiopasdfghjklzxcvbnm1234567890qwertyuiopasdfghjklzxcvbnm1234567890qwertyuiopasdfghjklzxcvbnm1234567890qwertyuiopaBVCRHSJAKL'); assert.strictEqual(test1Result, false, 'Test 1 failed'); // Test 2: Given a string with unique chars, it should return true const test2Result = isUniqueChars('kevin'); assert.strictEqual(test2Result, true, 'Test 2 failed'); // Test 3: Given a string with duplicate chars, it should return false const test3Result = isUniqueChars('mom'); assert.strictEqual(test3Result, false, 'Test 3 failed'); console.log('All tests passed.');

Solution

Accordion #1

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

See Solution

const isUniqueChars = (str) => {
  if (str.length > 128) return false;

  const charMap = new Map();

  for(const currentChar of str) {
    if (charMap.get(currentChar)) {
      return false;
    } else {
      charMap.set(currentChar, true);
    }
  }

  return true;
};

Explanation of solution

The above solution checks if a string has unique characters. It optimizes by rejecting strings longer than the character set (128 in this case). It uses a Map to track characters, returning false if a duplicate is found, or true if all characters are unique. Time complexity is O(N), space complexity is O(K) for unique characters.

If you want to optimize more, you can use an array of booleans to track character presence, offering improved space efficiency with a constant space complexity of O(1) compared to the Map-based solution’s variable space complexity.

const isUniqueChars = (str) => {
  if (str.length > 128) return false;

  const charSet = new Array(128).fill(false);

  for (const currentChar of str) {
    const charCode = currentChar.charCodeAt(0);
    if (charSet[charCode]) {
      return false;
    } else {
      charSet[charCode] = true;
    }
  }

  return true;
};