Click here to Skip to main content
Click here to Skip to main content

Tagged as

Go to top

How to check if a string has all unique characters?

, 15 Apr 2014
Rate this:
Please Sign up or sign in to vote.
The First solution that come 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 […

The First solution that come 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 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 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 then 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 value 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, lets 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 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.

License

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

Share

About the Author

Bhargav Kaneria
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).
Follow on   LinkedIn

Comments and Discussions

 
GeneralMy vote of 4 Pinmemberdmjm-h21-Apr-14 13:08 
SuggestionBetter but not the best PinprofessionalMember 1022724817-Apr-14 8:14 
GeneralRe: Better but not the best PinmemberBhargav Kaneria17-Apr-14 8:25 
GeneralRe: Better but not the best PinprofessionalMember 1022724819-Apr-14 5:08 
QuestionFind code here. PinmemberBhargav Kaneria17-Apr-14 7:46 
QuestionNice... But obvious, no? PinmemberMember 1038982117-Apr-14 7:11 
GeneralMy vote of 1 PinmemberAntonio Ripa17-Apr-14 1:55 
GeneralRe: My vote of 1 PinmemberWilliam E. Kempf17-Apr-14 2:21 
GeneralRe: My vote of 1 PinmemberAntonio Ripa17-Apr-14 2:36 
GeneralRe: My vote of 1 PinmemberWilliam E. Kempf17-Apr-14 8:18 
GeneralRe: My vote of 1 PinmemberAntonio Ripa17-Apr-14 8:42 
GeneralRe: My vote of 1 PinmemberWilliam E. Kempf17-Apr-14 10:40 
GeneralRe: My vote of 1 PinmemberAntonio Ripa17-Apr-14 12:33 
GeneralRe: My vote of 1 PinmemberWilliam E. Kempf18-Apr-14 2:29 
GeneralRe: My vote of 1 PinmemberBhargav Kaneria18-Apr-14 3:10 
GeneralRe: My vote of 1 PinmemberPeejayAdams22-Apr-14 4:45 
QuestionMost of the String related task can be achieved through reg-ex Pinmembersandeep pandey16-Apr-14 2:50 
AnswerRe: Most of the String related task can be achieved through reg-ex PinmemberWilliam E. Kempf16-Apr-14 8:01 
AnswerRe: Most of the String related task can be achieved through reg-ex PinmemberGastonV17-Apr-14 2:25 

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

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

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 16 Apr 2014
Article Copyright 2014 by Bhargav Kaneria
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid