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[256];
    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

Latest
Previous
Next Post »

Contact Form

Name

Email *

Message *