Uniqueness of a String

Using Bitwise Operators in Java

Interviewer: Write a function that determines if a string has all unique characters.

No problem. This seems like a pretty basic question, where a knee-jerk reaction might be to immediately implement a hash set like this:

    
import java.util.HashSet;

  boolean isUnique(String str) {
      // "apple" --> false
      HashSet<Character> hash = new HashSet<>();
      for (char c : str.toCharArray()) {
          if (hash.contains(c)) {
              return false;
          } else {
              hash.add(c);
          }
      }
      return true;
  }

The time complexity is O(n), where n is the length of the string, and space complexity of O(1), due to the fact that there are only 128 ASCII characters available for use.

But here one might pause to wonder if that was what the question was asking. Are these ASCII characters we are dealing with, in which case a maximum 128 characters is correct, or are we handling Unicode strings with 2²¹ possibilities? Can we use additional libraries?

Interviewer: Yes, ASCII characters, but only from lowercase ‘a’ through ‘z’. No additional libraries.

This is why asking questions is so important.

Okay, so no additional libraries. Now that we know that only characters ‘a’ through ‘z’ will be used, we can make a boolean array of 26 characters, like this:

boolean isUnique(String str) {
    // without external library
    if (str.length() > 26) {
      return false;
    }

    boolean[] boolArray = new boolean[26];

    for (int i = 0; i < str.length(); i++) {
        int value = str.charAt(i) - 'a';
        if (boolArray[value]) {
            return false;
        } else {
            boolArray[value] = true;
        }
    }
    return true;
}

The solution above consists of the same time and space complexity, although now space is limited to only 26 characters instead of 128. Also, now that this ‘a’ — ‘z’ limit is in place, we can add a boundary condition that checks if the string length is greater than 26. Great!

Interviewer: I forgot to add — no arrays.

Oh. Okay Interviewer, let’s rethink this. No HashSets, no arrays — I guess we’ll go primitive. Really primitive.

Java Primitive Data Type Sizes (source)

To represent 26 ones or zeros requires 26 bits. An int consists of 32 bits — this would be plenty to store the entire lowercase alphabet. Let’s replace the boolean array with an int:

int memoryInt = 0;

// 00000000 00000000 00000000 00000000

Just like the boolean array of size 26, we need to fill the corresponding ASCII value of the character in the int memory space with 1, or true.

To do this, we need to manipulate the bits in the memoryInt, and to do that, we need bitwise operation.

Basic Bitwise Logic (source)

Bitwise logic is similar to boolean logic:

• or: boolean || similar to bitwise |
• and: boolean && similar to bitwise &
• exclusive or: boolean/bitwise is ^
• not: boolean ! similar to bitwise ~

Two other important operations are bitwise shift right (>>) and left (<<):

How the shift left operates (source)

To set a bit at the desired location in our memoryInt, the bitwise or equals assignment |= operator will be needed, offset by the ASCII value of the character:

// example: the string is 'baa'. current character 'b' --------

int value = str.charAt(i) - 'a' 
// value = 1, move 1 place to the left in memory

memoryInt |= (1 << value)  
// 00000010

// current character 'a' --------------------------------------

value = str.charAt(i) - 'a' 
// value = 0, move 0 places to the left in memory

memoryInt |= (1 << value)  
// 00000010 --> 'b'
// 00000001 --> 'a'
// --------
// 00000011 --> memoryInt after bitwise '|', 'b' and 'a' spaces are filled

How can we check if a character is already represented in the memoryInt?

1. Access that bit in the memoryInt.

1 << value

2. Determine if this bit is 0 or 1.

memoryInt & (1 << value)

// next character is 'a'

// 00000011 --> memoryInt, 'b' and 'a' spaces are filled
// 00000001 --> 'a'
// --------
// 00000001 --> bitwise '&' operator seperates only the bit in question

3. If it’s 1 (or larger than int 0) return false.

if ((memoryInt & (1 << value)) > 0) {
  return false;
}

The complete function:

boolean isUnique(String str) {
    // without arrays or additional libraries
    if (str.length() > 26) {
      return false;
    }

    int memoryInt = 0;

    for (int i = 0; i < str.length(); i++) {
        int value = str.charAt(i) - 'a';
        if ((memoryInt & (1 << value)) > 0) {
            return false;
        } else {
            memoryInt |= (1 << value);
        }
    }
    return true;
}

With the same time and space complexity as the previous attempts, the bitwise solution technically uses less space than the rest (a boolean array takes more than 26 bits).

Interviewer: Great. Next time ask more questions first :)

Manipulating data in its most basic form is a great way to use space efficiently, often with greater precision and with fewer resources required.

Bitwise operators can also make a simple question much more interesting to solve and sheds light on the history of computer memory architecture.

Cinematic explanation of (and plea to understand) bitwise operators