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

String : Count Words

Question : (Asked to me during a phone interview)

Write a function to count the words in a string. (without using any in-built split functions. The only delimiter is space).

My Thought Process :

Right of the bat , Start counting space characters. But realized that this would fail if all the characters are spaces. Alright, rethink. Make $word_count =0; Start reading characters, if space, skip till next character not a space. Increment the $word_count. But this was also flawed (for input " some word "). So finally after a 2nd rethink. Here's my answer :

public static int word_count(String s1){
// Function to calculate number of words in a string
int count = 0;

if(s1 == null)
return count;

int i= 0 ;
while(i < s1.length()){

while(i <s1.length() && s1.charAt(i) == ' ')
i++;
if(i == s1.length())
break;
else
{
count++;
while(i<s1.length() && s1.charAt(i) != ' ')
i++;
}

}

return count;
}

Complexity :

Time : O(n) : n being number of characters.

Space: O(1) : Just one variable space needed.