Saturday, 27 May 2017

C++ Program to find the first Non-repeating character in a string

C++ Program and algorithm to find the first non-repeating character of  a string is given below and this question has been already asked in the interviews of following companies:-

Amazon, Goldman Sachs, DE shaw, MAQ software, MakeMyTrip, Payu, TejasNetwork, OLA, OATS System, Teradata, InfoEdge

Source:  geeksforgeeks

ALGORITHM:

1.  Declare an array arr[256]={0} /*initialize every element to zero */
2.  do For i=1 to len(string):
3.           arr[string[i]]=arr[string[i]]+1
4.  do For i=1 to len(string):
5.           if(arr[string[i]]==1):
6.                      char c=string[i]
7.                      break
8.  print 'c'.


Note:  we are using array of size 256 because we are indexing characters of string using their ASCII value. For more click here


PROGRAM:

#include <iostream>
#include <map>
#include <string.h>
using namespace std;

int main() 
{
 
 
       char string[100];
       int arr[256]={0};
       
          cout<<"\n\nEnter the String:\n\n";
       cin>>string;
       for(int j=0;j<strlen(string);j++)
       {
            arr[string[j]]++;
       }
       char c;
       for(int j=0;j<strlen(string);j++)
       {
            if(arr[string[j]]==1)
            {
                c=string[j];
                break;
            }
       }
       cout<<"\n\n";
       cout<<c<<"\n\n";

       
       return 0;
}


OUTPUT:



EmoticonEmoticon