Given a string, find its first non-repeating character in only One scan

Question

Given a string, find the first non-repeating character in it. For example, if the input string is “GeeksforGeeks”, then output should be ‘f’.

We can use string characters as index and build a count array. Following is the algorithm.

1. Scan the string from left to right and construct the count array or HashMap.

2. 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.

Above problem and algorithm is from GeeksForGeeks

But it requires two scan of an array. I want to find first non-repeating character in only one scan.
I implemented above algorithm Please check it also on Ideone:

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<Character, Integer> hashMap=new HashMap<Character, Integer>();
        //First Scan
        for(int i = 0; i <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<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");
    }    
}

GeeksforGeeks also suggest efficient method but I think it is also two scan. Following solution is from GeeksForGeeks

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#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 < 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 && result > 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;
}

Answer 1

You can store 2 arrays: count of each character and the first occurrence(and fill both of them during the first scan). Then the second scan will be unnecessary.

Answer 2

Use String functions of java then you find the solution in only one for loop The Example is show below

import java.util.Scanner;
public class firstoccurance {
public static void main(String args[]){
char [] a ={'h','h','l','l','o'};
//Scanner sc=new Scanner(System.in);
String s=new String(a);//sc.next();
char c;
int i;
int length=s.length();
for(i=0;i<length;i++)
{
    c=s.charAt(i);
    if(s.indexOf(c)==s.lastIndexOf(c))
    {
        System.out.println("first non repeating char in a string   "+c);
        break;
    }
    else if(i==length-1)
    {
        System.out.println("no single char");
    }
}
}
}

Answer 3

In following solution I declare one class CharCountAndPosition which stores firstIndex and frequencyOfchar. During the reading string characterwise, firstIndex stores the first encounter of character and frequencyOfchar stores the total occurrence of characters.

We will make array of CharCountAndPosition step:1 and Initialize it step2.
During scanning the string, Initialize the firstIndex and frequencyOfchar for every character step3.
Now In the step4 check the array of CharCountAndPosition, find the character with frequency==1 and minimum firstIndex
Over all time complexity is O(n+256), where n is size of string. O(n+256) is equivalent to O(n) Because 256 is constant. Please find solution of this on ideone

public class FirstNonRepeatedCharacterEfficient {
        public static void main(String [] args){
            // step1: make array of CharCountAndPosition.
            CharCountAndPosition [] array=new CharCountAndPosition[256];

            // step2: Initialize array with object of CharCountAndPosition. 
            for(int i=0;i<256;i++)
            {
                array[i]=new CharCountAndPosition();
            }

            Scanner scan=new Scanner(System.in);
            String str=scan.next();
            int len=str.length();
            // step 3
            for(int i=0;i<len;i++){
                char c=str.charAt(i);
                int index=c-'a';            
                int frequency=array[index].frequencyOfchar;
                if(frequency==0)
                    array[index].firstIndex=i;
                array[index].frequencyOfchar=frequency+1;    
                //System.out.println(c+" "+array[index].frequencyOfchar);
            }
            boolean flag=false;
            int firstPosition=Integer.MAX_VALUE;
            for(int i=0;i<256;i++){   

                // Step4         
                if(array[i].frequencyOfchar==1){
                    //System.out.println("character="+(char)(i+(int)'a'));
                    if(firstPosition> array[i].firstIndex){                    
                        firstPosition=array[i].firstIndex;
                        flag=true;
                    }
                }            
            }
            if(flag==true)
                System.out.println(str.charAt(firstPosition));
            else
                System.out.println("There is no such type of character");
        } 
    }
    class CharCountAndPosition{
        int firstIndex;
        int frequencyOfchar;
    }