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;jComplexity :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; }

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; }

## No comments:

## Post a Comment