How To Check if a String has All Unique Characters?

The first solution that comes to our mind is to convert the string to character array and sort them alphabetically and then check if two consecutive elements are equal or not. This is O(N * log N) operation.

Now the question is can this solution be improved?
And the answer is, YES.

So what is the solution?
Use HashSet.
Why?
Set is used to store unique values and that’s exactly what we need. Since we don’t need our elements to be ordered or sorted, we can use HashSet.
OK, how?
We can iterate through the character array of string and add each character to a HashSet as we encounter them. So if any character repeats, we should not be able to add that character to our HashSet and we know that string has duplicate characters!!!
This is a better solution as it runs in linear (O(n)) time as HashSet offers constant time performance for the add operation  and we only do one pass through string.
(Note: Refer to class HashSet and add method of class HashSet)

Yeah, it’s that simple.
So, let’s code that.

import java.util.*;

public class UniqueChecker1{

	public static void main(String[] args){

		String str = "bhargav";
		UniqueChecker1 uc = new UniqueChecker1();
		boolean result = uc.checkUnique(str);
		if(result)
			System.out.println("String has all unique characters");
		else
			System.out.println("String does not have all unique characters");
	}

	public boolean checkUnique(String str){

		HashSet hashSet = new HashSet(str.length());

		for(char c : str.toCharArray()){ //iterate through character array
			if(!hashSet.add(Character.toUpperCase(c)))//try to add each char to hashset
				return false; //return false if could not add
		}
		return true;
	}
}

Now, suppose we are asked not to use any of the data structures. then?
Can we do better than sorting the characters and then comparing? Yes.
How?
We can take an array of type boolean whose size will be 256 (assuming char set is ASCII), each element representing a character in char set.
Then, we can initialize this array with all false values and then for each character in the given string, we would set the corresponding boolean value to true.
So if that value is already true, then we know that the character is repeated and we stop!!! If we don’t find any true value until we reach the end of string, then we know that the string has all unique characters!!

This solution also runs in O(n).

Simple, right?

So, let's code this:

public class UniqueChecker2{

	public static void main(String[] args){

		String str = "bhargav";
		UniqueChecker2 uc = new UniqueChecker2();
		boolean result = uc.checkUnique(str);
		if(result)
			System.out.println("String has all unique characters");
		else
			System.out.println("String does not have all unique characters");
	}

	public boolean checkUnique(String str){

		boolean[] strSet = new boolean[256];//boolean array representing each character in char set

		for(int i = 0; i<str.length(); i++){

			int val = str.charAt(i);//we assign a character to an int so its ASCII value gets stored..!
			if(strSet[val]){ //if its already true
				return false; //we have a duplicate
			}
			strSet[val] = true; //set boolean value representing that character to be true
		}
		return true; // all characters in string was unique..!
	}
}

Note: In the above code, if char set is not ASCII, only array size need to be changed, the logic remains the same!
That’s it, if you find this post interesting, please share it. If you have any suggestions or doubts, please leave a comment below.

Thank you for reading.