Exploring Unique Character Detection

A question that you may get asked in a technical interview is to write a function that will determine if all characters in a string our unique. In this blog post, we'll examine multiple approaches to solving this problem using JavaScript. We'll start with a simple solution using a Set object, then dive into more efficient techniques involving bit manipulation.

The Problem

The task is to write a function that checks if all characters in a given string are unique. For instance, isCharactersUnique('foo') should return false, while isCharactersUnique('bar') should return true.

The Set Approach

Let's begin with a straightforward solution using a Set object to keep track of the characters we have already seen.

function isCharactersUnique(characters) {
  const foundCharacters = new Set();
  for (let character of characters) {
    if (foundCharacters.has(character)) {
      return false;
    }
    foundCharacters.add(character);
  }
  return true;
}

This approach is intuitive and easy to understand, making it suitable for most cases.

Bit Array Technique

For a potentially more efficient method, we can employ a bit array.

function isCharactersUnique(string) {
  string = string.toLowerCase();
  let counterTable = Number();
  for (const character of string) {
    const characterCode = character.charCodeAt() - "a".charCodeAt();
    const mask = 1 << characterCode;
    if (counterTable & mask) return false;
    counterTable |= mask;
  }
  return true;
}

Here, we assume that all characters in the string are lowercase. This technique involves using a bit array to keep track of the characters encountered, toggling bits based on character codes. This method can be more efficient in terms of space compared to the Set approach.

Handling a Larger Character Set

What if you need to handle a wider character set, such as the entire ASCII character set? The previous solution wouldn't work since we would get an integer overflow when shifting more than 32 bits. Instead, you can use an array containing four bit arrays.

function isCharactersUnique(string) {
  const counterTable = new Array(4).fill(0);
  for (const character of string) {
    const characterCode = character.charCodeAt();
    if (characterCode < 0 || characterCode > 127) {
      throw new Error("Invalid character code");
    }
    const bucketIndex = Math.floor(characterCode / 32);
    const index = characterCode % 32;

    const mask = 1 << index;
    if (counterTable[bucketIndex] & mask) {
      return false;
    }
    counterTable[bucketIndex] |= mask;
  }
  return true;
}

This approach efficiently handles the entire ASCII character set by organizing the characters into different bit arrays. We use floor division to determine which index in our array of bit arrays to use and then use the modulo operator to determine which bit to flip.

Conclusion

In this blog post, we delved into different techniques for determining if all characters in a string are unique. We discussed the Set approach, bit manipulation, and handling a broader character set. Depending on your specific requirements and constraints, you can choose the method that best suits your needs. By exploring various solutions, you enhance your problem-solving skills and open your mind to innovative ways to tackle challenges.