Skip to content

Instantly share code, notes, and snippets.

@Jeffwan
Created February 7, 2014 04:06
Show Gist options
  • Save Jeffwan/8857242 to your computer and use it in GitHub Desktop.
Save Jeffwan/8857242 to your computer and use it in GitHub Desktop.
Implement an algorithm to determine if a string has all unique characters. CC 150 - Arrays and Strings
package CC150.ArraysAndString;
import java.util.HashSet;
import java.util.Set;
public class IsUniqueChars {
public static void main(String args[]) {
System.out.println(isUniqueChars("abcdefghijklmnopqrstuvwxyz"));
}
/**
* Book's solution, just use boolean[] replaces Set, I need to understand unique characters!
* Then I could know I can create to boolean[256] to flag exist character.
*
* In additon, no need to conver string to charArray,just use charAt(), save some space
*
* Conclusion: 1.understand unicode & ascII character.(only 256 characters) 2. study using boolean[] as flag
* In my solution, I just judge str == null and str.length() ==0 but not use str.length() >256
*
*/
public static boolean isUniqueChars(String str) {
if (str.length() > 256) {
return false;
}
boolean[] flag = new boolean[256];
char temp;
for (int i=0; i<str.length(); i++) {
temp = str.charAt(i);
if(flag[temp]) {
return false;
} else {
flag[temp] = true;
}
}
return true;
}
/**
* Extra Data Structure Solution
* unique --> Set
*/
public static boolean isUniqueChars2(String str){
if (str == null) {
return false;
}
Set<Character> set = new HashSet<Character>();
char[] arr = str.toCharArray();
for (int i = 0; i < str.length(); i++) {
if(set.contains(arr[i])) {
return false;
} else {
set.add(arr[i]);
}
}
return true;
}
/**
* brute force solution
* No extra data structure and space but time complexity increase
*/
public static boolean isUniqueChars3(String str) {
if (str == null) {
return false;
}
char[] arr = str.toCharArray();
for (int i=0; i<arr.length; i++) {
for (int j=i+1; j<arr.length; j++) {
if (arr[i] == arr[j]) {
return false;
}
}
}
return true;
}
}
@totoro686
Copy link

if(flag[temp]) {
return false;
} else {
flag[temp] = true;
}

what is the logical in here?

For emample:
abcdefghijklmnopqrstuvwxyz

when i = 0,
temp = str.charAt(i) mean temp = a

flag[temp] mean what?

flag[a]?

when it will return false?

@sushmaGS-zz
Copy link

Hi totoro686, You might have already understood the code by now. Just want to say what I understood from the code.
The boolean array flag[] has all its fields set to false initially.
temp has the ith character of the string stored in it.
when checking uniqueness for each character of string,

if(flag[temp]) is equivalent to if(flag[temp] == true)
It means that particular field of array has already been occupied by the character we want to check which means we are accessing that character for the second time. so we will return false.

otherwise, we are seeing that character for the first time, so now we mark the flag as true so that for the next similar character when it comes to check that field it will be shown as true (means occupied).

@SethuVignesh
Copy link

The solution you have will work only for ASCII characters,
What about Strings which have 6000 unique characters.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment