fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef struct node
  5. {
  6.     char ch;
  7.     node *next;
  8. }node;
  9.  
  10.  
  11.  
  12.  
  13. char firstNotRepeatingCharacter(string &s)
  14. {
  15.   char ans = '_';
  16.   map<char,node*> mp;
  17.   node *head = NULL;
  18.   node *last;
  19.   node *temp1 = NULL;
  20.   node *temp2 = new node[1];
  21.   temp2->ch = '$';
  22.   temp2->next = NULL;
  23.   for(int i = 0;i < s.size();++i)
  24.   {
  25.     //cout << s[i] << endl;
  26.     //first occurence//
  27.     if(mp.find(s[i]) == mp.end())
  28.     {
  29.       node *temp = new node[1];
  30.       temp->ch = s[i];
  31.       temp->next = NULL;
  32.       if(head == NULL)
  33.       {
  34.         head = temp;
  35.         last = temp;
  36.         mp.insert(make_pair(s[i],temp1));
  37.       }
  38.       else
  39.       {
  40.         last->next = temp;
  41.         mp.insert(make_pair(s[i],last));
  42.         last = temp; 
  43.       }
  44.     }
  45.     //Repeated occurence//
  46.     else
  47.     {
  48.       node *temp = mp[s[i]];
  49.       if(mp[s[i]] != temp2)
  50.       {
  51.         if(temp == temp1)
  52.         {
  53.           head = head->next;
  54.           if((head)!=NULL){mp[head->ch] = temp1;}
  55.           else last = head;
  56.           mp[s[i]] = temp2;
  57.         }
  58.         else if((temp->next) != NULL)
  59.         {
  60.           temp->next = temp->next->next;
  61.           if((temp->next) != NULL){mp[temp->next->ch] = temp;}
  62.           else last = temp;
  63.           mp[s[i]] = temp2;
  64.         }
  65.         else
  66.         {
  67.           ;
  68.         }
  69.      }
  70.     }
  71.     /*node *temp2 = head;
  72.     while(temp2 != NULL){cout << temp2->ch << "--";temp2 = temp2->next;}
  73.     cout << endl;*/
  74.   }
  75.   if(head == NULL){;}
  76.   else {ans = head->ch;}
  77.   return ans;
  78. }
  79.  
  80. int main()
  81. {
  82.   int T;
  83.   cin >> T;
  84.   while(T--)
  85.   {
  86.   string str;
  87.   cin >> str;
  88.   cout << str << " ->  " << firstNotRepeatingCharacter(str)<< endl;
  89.   }
  90.   return 0;
  91. }
Success #stdin #stdout 0s 15240KB
comments ()
stdin 
10
abacabad
abacabaabacaba
z
bcb
bcccccccb
abcdefghijklmnopqrstuvwxyziflskecznslkjfabe
zzz
bcccccccccccccyb
xdnxxlvupzuwgigeqjggosgljuhliybkjpibyatofcjbfxwtalc
ngrhhqbhnsipkcoqjyviikvxbxyphsnjpdxkhtadltsuxbfbrkof
stdout 
abacabad ->  c
abacabaabacaba ->  _
z ->  z
bcb ->  c
bcccccccb ->  _
abcdefghijklmnopqrstuvwxyziflskecznslkjfabe ->  d
zzz ->  _
bcccccccccccccyb ->  y
xdnxxlvupzuwgigeqjggosgljuhliybkjpibyatofcjbfxwtalc ->  d
ngrhhqbhnsipkcoqjyviikvxbxyphsnjpdxkhtadltsuxbfbrkof ->  g
https://ideone.com/l2fj2x
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!