12,632,959 members (32,603 online)
Technical Blog
alternative version

24.6K views
2 bookmarked
Posted

# How To Check if a String has All Unique Characters?

, 15 Apr 2014 CPOL
 Rate this:
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?

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

## Share

 Software Developer (Junior) 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).

## You may also be interested in...

 Pro Pro

 First Prev Next
 My vote of 4 dmjm-h21-Apr-14 14:08 dmjm-h 21-Apr-14 14:08
 Better but not the best Member 1022724817-Apr-14 9:14 Member 10227248 17-Apr-14 9:14
 Re: Better but not the best Bhargav Kaneria17-Apr-14 9:25 Bhargav Kaneria 17-Apr-14 9:25
 Re: Better but not the best Member 1022724819-Apr-14 6:08 Member 10227248 19-Apr-14 6:08
 Find code here. Bhargav Kaneria17-Apr-14 8:46 Bhargav Kaneria 17-Apr-14 8:46
 Nice... But obvious, no? Member 1038982117-Apr-14 8:11 Member 10389821 17-Apr-14 8:11
 My vote of 1 Antonio Ripa17-Apr-14 2:55 Antonio Ripa 17-Apr-14 2:55
 Re: My vote of 1 William E. Kempf17-Apr-14 3:21 William E. Kempf 17-Apr-14 3:21
 Re: My vote of 1 Antonio Ripa17-Apr-14 3:36 Antonio Ripa 17-Apr-14 3:36
 Re: My vote of 1 William E. Kempf17-Apr-14 9:18 William E. Kempf 17-Apr-14 9:18
 Re: My vote of 1 Antonio Ripa17-Apr-14 9:42 Antonio Ripa 17-Apr-14 9:42
 Re: My vote of 1 William E. Kempf17-Apr-14 11:40 William E. Kempf 17-Apr-14 11:40
 Re: My vote of 1 Antonio Ripa17-Apr-14 13:33 Antonio Ripa 17-Apr-14 13:33
 Re: My vote of 1 William E. Kempf18-Apr-14 3:29 William E. Kempf 18-Apr-14 3:29
 Re: My vote of 1 Bhargav Kaneria18-Apr-14 4:10 Bhargav Kaneria 18-Apr-14 4:10
 Most of the String related task can be achieved through reg-ex sandeep pandey16-Apr-14 3:50 sandeep pandey 16-Apr-14 3:50
 Re: Most of the String related task can be achieved through reg-ex William E. Kempf16-Apr-14 9:01 William E. Kempf 16-Apr-14 9:01
 Re: Most of the String related task can be achieved through reg-ex GastonV17-Apr-14 3:25 GastonV 17-Apr-14 3:25
 Last Visit: 31-Dec-99 19:00     Last Update: 8-Dec-16 20:43 Refresh 1