[Google Interview] No. 13 - First Character Appearing Only Once

Problem: Implement a function to find the first character in a string which only appears once.

For example: It returns ‘b’ when the input is “abaccdeff”.

Example Code O(n):

#include <stdlib.h>

#include <stdio.h>

char getFirstCharacter(char *input, int len)

{

#define MAX_BUCKET_SIZE 256

        char hash[MAX_BUCKET_SIZE];

        char res=0;

        memset(hash, 0x00, sizeof(hash));

        // walk through all the characters

        int i;

        for (i=0; i<len; i++)

        {
                if (hash[input[i]] < 3) // to avoid overflow in hash item
                {

                    hash[input[i]]++;
                }

        }

        for (i=0; i<len; i++)

        {

                if (hash[input[i]] == 1)

                {

                        res = input[i];

                        break;

                }

        }

        return res;

}

int main(int argc, char **argv)

{

        char *input="abaccdeff";

        char first=0;

        first = getFirstCharacter(input, sizeof(input)/sizeof(input[0]));

        printf("first char is = %c(%02x)\n", first, first);

        return 0;

}

ref: http://codercareer.blogspot.tw/2011/10/no-13-first-character-appearing-only.html