Problem

Implement an algorithm to determine if a string has all unique characters.

Solution

Method 1 - Brute Force - Compare All Characters

Brute force way can be we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop.

Code

Cpp
bool areAllCharsUnique(string myString) {
  for (int i = 0; i < myString.length(); i++) {
    for (int j = 0; j < myString.length(); j++) {
      if (myString[i] == myString[j] && i != j) {
        return false;
      }
    }
  }
  return true;
}
Java
boolean areAllCharsUnique(String myString) {
	for (int i = 0; i < myString.length(); i++) {
		for (int j = 0; j < myString.length(); j++) {
			if (myString.charAt(i) == myString.charAt(j) && i != j) {
				return false;
			}
		}
	}

	return true;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Improvements

This code is very simple, but there are some problems. First, comparisons are repeated. Let’s say we have a string of five characters, and the string is “ABCDE”. On the first iteration, we will compare A to B, then to C, then to D, then to E. On the second iteration, we will compare B to A, then to C, then to D, then to D. Do you see how the comparison between A and B is repeated on the second iteration?

We can optimize this code a bit by altering the loops so that each character is only compared to every character AFTER it. This would mean that once A is compared to all the other characters, the other characters never compare themselves to A again.

bool areAllCharsUnique(string myString){
 for (int x = 0; x < myString.length() - 1; x++) {
	 for (int y = x + 1; y < myString.length(); y++) {
	 	if (myString[x] == myString[y]) return false;
	 }
 }
 return true;
}

Time complexity - O(n^2)…still bad

Method 2 - Using the 256 Length Array Assuming the String is an Ascii Character

  1. Create an int array [0-255], one for each character index, initialized to zero.
  2. Loop through each character in the string and increment the respective array position for that character
  3. If the array position already contains a 1, then that character has already been encountered. Result => Not unique.
  4. If you reach the endof the string with no occurrence of(3), Result => the string is unique.

Here is the function in java

public boolean areAllCharsUnique(String s) {
 boolean[] mask = new boolean[256];
 for (int i = 0; i < s.length(); i++) {
	 if (mask[s.charAt(i)]){
	 	return false;
	 }
	 mask[s.charAt(i)] = true;
 }
 return true;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1) (O(256) ⇨ O(1))

Method 3 - Sorting the Array and Then Finding Unique Chars

Here using the sorting algorithm to sort the string first, then compare every pair of neighboring characters to see if they are the same.  The main time consuming are sorting array + neighborhood comparisions.

Code

Java

Java uses merge sort for object type arrays, and quicksort for primitive data types. Also for efficiency, it would switch to insertion sort when fewer than seven array elements are being sorted. So, time complexity in general is O(nlogn).

public boolean areAllCharsUnique(String s) {
 char[] chars = s.toCharArray();
 Arrays.sort(chars);
 for (int i = 0; i < chars.length - 1; i++) {
	 if (chars[i] == chars[i + 1]) {
		 return false;
	 }
 }
 return true;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)

What if not use additional data structure?

Method 1 and method 3 still work here. But in the interview if someone gives you a restricted string which can have only say ‘a’ and ‘z’ and asks you to not use any data structure then? Then we can also use bit manipulation, as explained here as solution 4: https://k2code.blogspot.com/2014/03/determine-if-string-has-all-unique.html.