# Determine if a String has all Unique Characters

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

Example:
The String "Hello" has two "l"s. Therefore, it does not have all unique characters. On the other hand, if you consider the String "World", it is formed using all unique characters.

Break Down:
Let's write a class named TestUniqueness which has a method isUnique which can be called from the main method as given below:
``````public class TestUniqueness {

public static void main(String[] args) {
System.out.println(isUnique("hello"));
System.out.println(isUnique("world"));
}

public static boolean isUnique(String text) {
return false;
}
}``````
Of course, you can write a fancy code to read user input and feed them to an `isUnique` method. However, to keep the code clean and simple, I am calling the static method `isUnique` and immediately print the response. The `isUnique` method returns false all the times. In the following section, we are going to implement the algorithm for the isUnique method.

Solution 1:
The straightforward solution to this problem is reading the String, character by character and check whether the selected character appears in the remaining String.
``````public static boolean isUnique(String text) {
final int size = text.length();
// Iterate from the first character to the second last
for (int i = 0; i < size - 1; i++) {
char selectedChar = text.charAt(i);
// Compare the character with the remaining characters
for (int j = i + 1; j < size; j++) {
if (selectedChar == text.charAt(j)) {
return false;
}
}
}
return true;
}``````
The above method has two nested for-loops. Given a String with n number of characters, the outer loop iterates n - 1 times. The inner loop iterates n - 1 times for the first time, n - 2 times for the second time, n - 3 times for the third time and only one time for the last time. So the time complexity can be written as:
``````T(n) = O(n - 1) + O (n - 2) + O(n - 3) + ... + 2 + 1
= O(n - 1) * O(n) / 2
= O(n2)``````

Solution 2:
Using a sorting algorithm that can sort an array of characters in less than O(n2) time complexity can reduce the time complexity of the isUnique method. In a sorted array, if there are duplicate elements, they should be adjacent to each other. Using a loop, adjacent elements can be compared as given below:
``````public static boolean isUnique(String text) {
char[] characters = text.toCharArray();
// Arrays.sort (DualPivotQuicksort algorithm) sorts arrays in O(nlog(n))
Arrays.sort(characters);
int size = characters.length - 1;
for (int i = 0; i < size; i++) {
if (characters[i] == characters[i + 1]) {
return false;
}
}
return true;
}``````
The time complexity of the above method can be written as given below:
``````T(n) = O(nlog(n)) + O (n)
= O(nlog(n))``````

Solution 3:
If the String is formed using only ASCII characters, an efficient solution can be designed using an array. There are 256 ASCII characters. Knowing the range of characters lets us define an array with 256 elements and to keep the record of the occurrence of characters.
``````public static boolean isUnique(String text) {
int size = text.length();
if (size > 256) {
// Using unique 256 characters, one cannot create a text with more than 256 characters
return false;
}
boolean[] characters = new boolean;
for (int i = 0; i < size; i++) {
int asciiValue = text.charAt(i);
if (characters[asciiValue]) {
// This ASCII value is already noted
return false;
}
// Note the ASCII value
characters[asciiValue] = true;
}
return true;
}``````
There is a for loop iterates for n number of times where n is the number of characters in the String. Therefore the complexity of the algorithm is O(n). However, the if condition at the beginning of the method returns immediately if the String has more than 256 characters. Therefore, I would define the time complexity of the algorithm as given below:
``````T(n) = O(n) -- if n <= 256
O(1) -- if n >  256
``````

Solution 4:
There is a variation of this question. Given a String with only characters from `'a'` to `'z'`, you may be asked to modify the above solution without using a datastructure (We use an array in Solution 3). Have a look at the following code:
``````public static boolean isUnique(String text) {
int size = text.length();
if (size > 26) {
return false;
}
int flagBoard = 0;  // 32 bit data type which means there are 32 bits
for (int i = 0; i < size; i++) {
// In ASCII 'a' = 97, 'b' = '96' and so on
int index = text.charAt(i) - 'a';   // The range of index is 0 - 26
int binaryIndex = 1 << index;   // Index of 1 in binary represents the character
if ((flagBoard & binaryIndex) > 0) {
// This ASCII value is already noted
return false;
}
// Note the ASCII value
flagBoard = flagBoard | binaryIndex;
}
return true;
}``````
The solution to this problem is tricky at first glance, but it is quite similar to Solution 3. ASCII value of 'a' is 97, 'b' is 98, and 'z' is 122. Therefore the range of `index` is 0 - 25. Shifting 1 to left by `index` number of times creates a binary number with a leading 1 and `index` number of 0s. For example, if the character is 'd', `index` will be 3 and `binaryIndex` will be `10002` in binary. As you can see the position of '1' from the right indicates the index of the character. Initially, `flagBoard` is 32 0s in binary. The `&` operator is used to check if the `flagBoard` and `binaryIndex` have 1 at the same position. The `|` operator is used to set 1 at the index of the character. This way, we use an int as an array with 32 elements and set 1 at the index of the character which is quite similar to Solution 3 in which we used a boolean array and set true at the index of the character. Time complexity of this algorithm is given below:
``````T(n) = O(n) -- if n <= 26
O(1) -- if n >  26
``````

Previous
Next Post »

Name

Email *

Message *