Click here to Skip to main content
15,867,832 members
Articles / General Programming / String

How To Check if a String has All Unique Characters?

Rate me:
Please Sign up or sign in to vote.
3.83/5 (5 votes)
15 Apr 2014CPOL2 min read 46.7K   2   19
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.

Java
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:

Java
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Junior)
India India
Hi, I’m Bhargav Kaneria. I live in Pune, India. By profession I am a young software
developer(Trainee). I like to learn new languages(obviously programming!). I’m comfortable in Java. I also have some knowledge of Ruby, Groovy and a bit of JavaScript(learning currently) and a bit of PHP. My area of interests include programming(duh!), Internet, data structures and algorithms, economics and history(mostly related to world war II).

Comments and Discussions

 
GeneralMy vote of 4 Pin
dmjm-h21-Apr-14 13:08
dmjm-h21-Apr-14 13:08 
SuggestionBetter but not the best Pin
Member 1022724817-Apr-14 8:14
professionalMember 1022724817-Apr-14 8:14 
GeneralRe: Better but not the best Pin
Bhargav Kaneria17-Apr-14 8:25
Bhargav Kaneria17-Apr-14 8:25 
GeneralRe: Better but not the best Pin
Member 1022724819-Apr-14 5:08
professionalMember 1022724819-Apr-14 5:08 
QuestionFind code here. Pin
Bhargav Kaneria17-Apr-14 7:46
Bhargav Kaneria17-Apr-14 7:46 
QuestionNice... But obvious, no? Pin
Kirk 1038982117-Apr-14 7:11
Kirk 1038982117-Apr-14 7:11 
GeneralMy vote of 1 Pin
Antonio Ripa17-Apr-14 1:55
professionalAntonio Ripa17-Apr-14 1:55 
GeneralRe: My vote of 1 Pin
William E. Kempf17-Apr-14 2:21
William E. Kempf17-Apr-14 2:21 
GeneralRe: My vote of 1 Pin
Antonio Ripa17-Apr-14 2:36
professionalAntonio Ripa17-Apr-14 2:36 
GeneralRe: My vote of 1 Pin
William E. Kempf17-Apr-14 8:18
William E. Kempf17-Apr-14 8:18 
I didn't "wrote about a silly tips implemented using Java". I didn't write the article. I'm also not confused. Hash tables are a well known algorithm. Building another algorithm on top of that seems to me to still be a general purpose algorithm. You seem to be picking nits in your down vote here.
William E. Kempf

GeneralRe: My vote of 1 Pin
Antonio Ripa17-Apr-14 8:42
professionalAntonio Ripa17-Apr-14 8:42 
GeneralRe: My vote of 1 Pin
William E. Kempf17-Apr-14 10:40
William E. Kempf17-Apr-14 10:40 
GeneralRe: My vote of 1 Pin
Antonio Ripa17-Apr-14 12:33
professionalAntonio Ripa17-Apr-14 12:33 
GeneralRe: My vote of 1 Pin
William E. Kempf18-Apr-14 2:29
William E. Kempf18-Apr-14 2:29 
GeneralRe: My vote of 1 Pin
Bhargav Kaneria18-Apr-14 3:10
Bhargav Kaneria18-Apr-14 3:10 
GeneralRe: My vote of 1 Pin
PeejayAdams22-Apr-14 4:45
PeejayAdams22-Apr-14 4:45 
QuestionMost of the String related task can be achieved through reg-ex Pin
sandeep pandey16-Apr-14 2:50
sandeep pandey16-Apr-14 2:50 
AnswerRe: Most of the String related task can be achieved through reg-ex Pin
William E. Kempf16-Apr-14 8:01
William E. Kempf16-Apr-14 8:01 
AnswerRe: Most of the String related task can be achieved through reg-ex Pin
Gaston Verelst17-Apr-14 2:25
Gaston Verelst17-Apr-14 2:25 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.