String : Anagrams or not

Question : Find if two words are anagrams or not.

Solution :
The best solution basically involves sorting the characters in the words and then comparing to check if they are same.


public static boolean isAnagram(String s1, String s2){
      
        if (s1.length() != s2.length() )
            return false;
      
        char s1array[] = s1.toLowerCase().toCharArray();
        char s2array[] = s2.toLowerCase().toCharArray();
      
        Arrays.sort(s1array);
        Arrays.sort(s2array);
      
        for (int i=0;i <s1.length();i++)
            if (s1array[i] != s2array[i])
                return false;
        return true;
    }

String : Remove duplicate characters

Question : Remove Duplicate characters from a string.

Solution :

Basically the solution involves counting the occurences of characters in the string .

First solution uses an in-built Hashtable :

    public static String removeDuplicateCharHash(String ip){
        Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();
        String op = new String("");
        for(int i=0;i<ip.length();i++){
            Character ch = ip.charAt(i);
            if (! ht.containsKey(ch))
            { op = op + ch; ht.put(ch, new Integer(1)); }
        }
        return op;
    }
   
Second Solution uses a bit vector which is used as a hastable:

    public static String removeDuplicateChar(String ip){
// Initialize the bit vector  
    int ht[] = new int[256];
        for (int i=0;i<256;i++)
            ht[i] = 0;
     
  String op = "";
       
        for (int i=0;i<ip.length();i++){
            char ch = ip.charAt(i);
            if (ht[ch] == 0)
            {op = op + ch; ht[ch]++;}
        }
       
        return op;
    }

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.