String : has Unique characters.

Question: Implement a function to find if a string has all unique characters.

Thought Process : Basically, you have to note if any character has been repeated or not. So a list of used character has to be maintained. So we can utilize a Hash table for such a purpose. However, in this particular case, we can emulate a hash table by using an array (the characters value can be the index and the value can be 1 or 0) ! So two solutions :

public static boolean unique_chars(String s){
int ht[] = new int[256];
for(int i=0;i<256;i++)
   ht[i] = 0;
  
  for(int j=0;j 0){
return false;
}
ht[(int)s.charAt(j)]++;
}
return true;
}

public static boolean unique_chars_hash(String s){
Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();

for(int j=0;j<s.length();j++){
if(ht.containsKey(s.charAt(j))){
return false;
}
ht.put(s.charAt(j), new Integer(1));
}
return true;
}

Complexity :
Time : O(n) : where n is the number of characters.
Space: O(1) : You would need extra storage for an array to emulate the hashtable but that will be constant. You can even reduce that space by using a bit vector.

public static boolean unique_chars_bv(String s){
  // Assuming all lowercase characters
  int bv =0;
  
  for(int j=0;j<s.length();j++){
   if((bv & (1<<(int)s.charAt(j))) > 0){
    return false;
   }
   bv |= (1<<(int)s.charAt(j));
  }
   return true;
 }