title: Given a string, find its first non-repeating character in only One scan
body: <blockquote>
    <p>Given a string, find the first non-repeating character in it. For
    example, if the input string is “GeeksforGeeks”, then output should be
    ‘f’. </p>
    
    <p>We can use string characters as index and build a count array.
    Following is the algorithm.</p>
    
    <ol>
    <li><p>Scan the string from left to right and construct the count array or
    HashMap.  </p></li>
    <li><p>Again, scan the string from left to right and check for
    count of each  character, if you find an element who's count is 1,
    return it.</p></li>
    </ol>
  </blockquote>
  
  <p>Above problem and algorithm is from <a href="http://www.geeksforgeeks.org/given-a-string-find-its-first-non-repeating-character/" rel="nofollow noreferrer">GeeksForGeeks</a> </p>
  
  <p><strong>But it requires two scan of an array. I want to find first non-repeating character in only one scan.</strong><br>
  I implemented above algorithm <a href="http://ideone.com/amNcli" rel="nofollow noreferrer">Please check it also on Ideone</a>:</p>
  
  <pre><code>import java.util.HashMap;
  import java.util.Scanner;
  
  /**
   *
   * @author Neelabh
   */
  public class FirstNonRepeatedCharacter {
      public static void main(String [] args){
          Scanner scan=new Scanner(System.in);
          String string=scan.next();
          int len=string.length();
          HashMap&lt;Character, Integer&gt; hashMap=new HashMap&lt;Character, Integer&gt;();
          //First Scan
          for(int i = 0; i &lt;len;i++){
              char currentCharacter=string.charAt(i);
              if(!hashMap.containsKey(currentCharacter)){
                  hashMap.put(currentCharacter, 1);
              }
              else{
                  hashMap.put(currentCharacter, hashMap.get(currentCharacter)+1);
              }
          }
          // Second Scan
          boolean flag=false;
          char firstNonRepeatingChar = 0;
          for(int i=0;i&lt;len;i++){
                  char c=string.charAt(i);
                  if(hashMap.get(c)==1){
                      flag=true;
                      firstNonRepeatingChar=c;
                      break;
                  }
          }
          if(flag==true)
              System.out.println("firstNonRepeatingChar is "+firstNonRepeatingChar);
          else
              System.out.println("There is no such type of character");
      }    
  }
  </code></pre>
  
  <p>GeeksforGeeks also suggest efficient method but I think it is also <em>two scan</em>. Following solution is from <a href="http://www.geeksforgeeks.org/given-a-string-find-its-first-non-repeating-character/" rel="nofollow noreferrer">GeeksForGeeks</a></p>
  
  <blockquote>
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;limits.h&gt;
  #define NO_OF_CHARS 256
  
  // Structure to store count of a character and index of the first
  // occurrence in the input string
  struct countIndex {
     int count;
     int index;
  };
  
  /* Returns an array of above structure type. The size of
     array is NO_OF_CHARS */
  struct countIndex *getCharCountArray(char *str)
  {
     struct countIndex *count =
          (struct countIndex *)calloc(sizeof(countIndex), NO_OF_CHARS);
     int i;
  
     // This is First Scan
  
     for (i = 0; *(str+i);  i++)
     {
        (count[*(str+i)].count)++;
  
        // If it's first occurrence, then store the index
        if (count[*(str+i)].count == 1)
           count[*(str+i)].index = i;
     }
     return count;
  }
  
  /* The function returns index of the first non-repeating
      character in a string. If all characters are repeating
      then reurns INT_MAX */
  int firstNonRepeating(char *str)
  {
    struct countIndex *count = getCharCountArray(str);
    int result = INT_MAX, i;
  
    //Second Scan
    for (i = 0; i &lt; NO_OF_CHARS;  i++)
    {
      // If this character occurs only once and appears
      // before the current result, then update the result
      if (count[i].count == 1 &amp;&amp; result &gt; count[i].index)
         result = count[i].index;
    }
  
    free(count); // To avoid memory leak
    return result;
  }
  
  
  /* Driver program to test above function */
  int main()
  {
    char str[] = "geeksforgeeks";
    int index =  firstNonRepeating(str);
    if (index == INT_MAX)
      printf("Either all characters are repeating or string is empty");
    else
     printf("First non-repeating character is %c", str[index]);
    getchar();
    return 0;
  }
  </code></pre>
  </blockquote>