Strings

Question: For a given string, find its first non-repeating character?

Algorithm1: 
Step1: Make an array of 256,
Step2: Count frequency of all character and store in array. Here characters ASCII value is used as index.
Step3: Now again scan the string character by character, and check the frequency of current character. If it is one just break loop and return the first non-repeating character.

Time Complexity is O(n)+O(n)=O(n), but required two scan of given strings. Please remember here we required to scan string two times.

Algorithm2: 

Step1: Declare Data Structure which takes two fields 1. count, 2. index. count will be the frequency of characters and index is the index of character which occurs first time.  

class countCharAndIndex{
      int count;
      int index;
}

Step2: First make an array of countCharAndIndex. And  scan the string and count the frequency of each character and store the index, when any character occurs first time.

    a. countCharAndIndex [] array=new countCharAndIndex[256];
    b. For i=0 to length of countCharAndIndex-1.
           array[str.charAt(i)].count++;
           if(array[str.charAt(i)].count==1)// char str.charAt(i) occur first time
                 array[str.charAt(i)].index=i;
        return array;
  
   Here we need one scan of string.

Step3: Here we need only scan of array, whose length is 256.
   a. result=MAX
   b. for i=0 to 255
           if((array[i].count==1) && (array[i].index<result))
                    result=array[i].index;
       return result.

Time complexity is only O(n)+256=O(n), only one almost one scan.