Strings & Arrays - Unique Characters

There are several ways to figure out whether a string has all unique characters.

In my opinion, the best way is to use a bit vector. This will include some basic knowledge of bit arithmetic. So let's quickly remember some basic bit logic.

• 1 | 0 = 1
• 0 | 0 = 0
• 1 | 1 = 1

• 1 & 0 = 0
• 0 & 0 = 0
• 1 & 1 = 1

So let's dig into some actual code.

public boolean hasUniqueChars(String word) {
  int checker = 0;
  for (int i = 0; i < word.length(); i++) {
    int val = word.charAt(i) - 'a';
    int mask = (1 << val);
    if ((checker & mask) > 0) {
      return false;
    }
    checker = checker | mask;
  }
  return true;
}

One of the main things to note here is the mask variable and val. First off -- this code assumes that the letters we're dealing with are lower case a-z. The TL;DR as to what's happening here is that we loop through each letter in the string, and create a value from the difference between that letter and the first possible character in the range, in this case being 'a'. We're using ASCII codes to create this value. Whatever val gets set to, we use that value to set the mask. The mask is then checked against checker and if there's a "collision", meaning the value already exists, checker will be greater than 0. If there's no collision, then checker is 'or-ed' against the mask and where there is a 1 in the binary represenation of val.

Let's write out what happens in binary with the string "sas".
First loop, 's'

      int val = word.charAt('s') - 'a'; // will result in 0b10010 (18)
      int mask = (1 << val); // will result in 0b1000000000000000000 (262144)
      checker & mask > 0 // will result in false since there are no (1 & 1) being compared
      checker = checker | mask; // will result in 0b1000000000000000000 (262144)
    

      int val = word.charAt('a') - 'a'; // will result in 0b00000 (0)
      int mask = (1 << val); // will result in 0b0000000000000000001 (1)
      checker & mask > 0 // will result in false since there are no (1 & 1) being compared
      checker = checker | mask; // will result in 0b1000000000000000001 (262145)
    

      int val = word.charAt('s') - 'a'; // will result in 0b10010 (18)
      int mask = (1 << val); // will result in 0b1000000000000000000 (262144)
      checker & mask > 0 // will result in true since there is a 1 in checker and val, thus a collision