Finding the first non repeating character in a string

We have to do this in linear time – O(n) and constant extra space- O(1)

Assuming that the character set is ASCII, the number of characters possible are 256. This will differ if the string contains non-ASCII characters like Unicode.

First we declare a count array of size 256 which will keep track of the count of each character appearing in the given string. We use the character itself as an index into the count array. This will give the O(1) time complexity for accessing the count of that character.

For example we store the count of a character ‘a’ (ASCII value= 98) in count[98]. 

In the first iteration, we iterate over each character of the string and update it’s count in the array.

In the next iteration, we go through each character of the array and checking the count of it from the array. The first character that we encounter with the count 1 will be the required answer.

For example if the given input is “this is a test”

the count array will be 
a – 1
e – 1
h – 1
i – 2
s – 3
t – 3

The first character with count=1 is h.

Here is the Java implementation of the above algorithm. 

/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 8/25/13
 * Time: 4:22 PM
 */
import java.util.Scanner;
public class Main {
    public static void main(String[] args)
    {
        Scanner reader = new Scanner(System.in);
        String input = reader.nextLine();
        int ind = getFirstNonRepeating(input);
        if( ind != -1)
        {
            System.out.println(input.charAt(ind));
        }
        else
        {
            System.out.println("All characters are repeated");
        }
    }
    public static int getFirstNonRepeating(String input)
    {
        int[] charCount = new int[256];
        int i;
        for( i = 0; i < input.length(); i++)
        { 

             //we use the character itself as an index.

             charCount[ input.charAt(i) ]++;
        }
        for( i = 0; i < input.length(); i++)
        {
            if( charCount[ input.charAt(i) ] == 1)
                return i;
        }
        return -1;
    }
}