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

Question

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

Answer 1

1: Construct character count array from the input string.

  count['a'] = 2
  count['b'] = 1
  count['c'] = 2
  count['d'] = 2
  count['e'] = 1
  count['f'] = 2
  ……

2: Get the first character who's count is 1 ('b').

/* Returns an array of size 256 containg count of characters in the passed char array */

#define NO_OF_CHARS 256
int *getCharCountArray(char *str)
{
   int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);
   int i;
   for (i = 0; *(str+i);  i++)
      count[*(str+i)]++;
   return count;
}

/* The function returns index of first non-repeating character in a string. If all characters are repeating
then returns -1 */

int firstNonRepeating(char *str)
{
  int *count = getCharCountArray(str);
  int index = -1, i;

  for (i = 0; *(str+i);  i++)
  {
    if (count[*(str+i)] == 1)
    {
      index = i;
      break;
    }   
  }  

  free(count); // To avoid memory leak
  return index;
}

/* Driver program to test above function */

int main()
{
  char str[] = "abaccdeff";
  int index =  firstNonRepeating(str);
  if (index == -1)  
    printf("Either all characters are repeating or string is empty");
  else
   printf("First non-repeating character is %c", str[index]);
  getchar();
  return 0;
}

Credit: geeksforgeeks

Answer 2

Algorithm : scan through the string and update array when the character is occurred first time add it to vector, Now scan through the vector until the number of times the character occurred is 1.

Time Complexity : O(Length of string)
Space Complexity : O(Length of string)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    string s;
    cin >> s;
    vector<char> v;
    int *a = new int[256];
    for(int i=0; i<256; i++)
    {
        a[i] = 0;
    }
    for(int i=0; i<s.length(); i++)
    {
        if(a[(int)s[i]] == 0)
        {
            v.push_back(s[i]);
            a[(int)s[i]]++;
        }
        else
        {
            a[(int)s[i]]++;
        }
    }
    for(int i=0; i<v.size(); i++)
    {
        if(a[(int)v[i]] == 1) 
        {
            cout << v[i] << endl;
            break;
        }
    }
}