top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+6 votes
915 views

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

posted Dec 12, 2013 by Anuj Yadav

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

0 votes

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 Dec 12, 2013 by Satish Mishra
0 votes

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;
        }
    }
}
answer Dec 12, 2013 by Raghu
...