fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Node{
  5. public:
  6. 	int idx, cnt;
  7. 	char chr;
  8. 	Node(int i, int freq, char c) : idx(i), cnt(freq), chr(c){}
  9. };
  10.  
  11. void increaseKey(vector<Node> &heap, vector<int> &pos, int i){
  12. 	while(i && heap[i].cnt < heap[(i-1)/2].cnt){
  13.  
  14. 		swap(heap[i], heap[(i-1)/2]);
  15. 		swap(pos[heap[i].chr - 'a'], pos[heap[(i-1)/2].chr - 'a']);
  16.  
  17. 		i = (i-1)/2;
  18. 	}
  19. }
  20.  
  21. void heapify(vector<Node> &heap, vector<int> &pos, int i, int n){
  22. 	int small = i;
  23. 	int l = 2 * i + 1, r = l + 1;
  24.  
  25. 	if(l < n && heap[l].cnt < heap[small].cnt)
  26. 		small = l;
  27.  
  28. 	if(r < n && heap[r].cnt < heap[small].cnt)
  29. 		small = r;
  30.  
  31. 	if(small ^ i){
  32. 		swap(heap[i], heap[small]);
  33. 		swap(pos[heap[i].chr - 'a'], pos[heap[small].chr - 'a']);
  34.  
  35. 		heapify(heap, pos, small, n);
  36. 	}	
  37. }
  38.  
  39. int main() {
  40. 	char val;
  41. 	vector<int> position(26, -1);
  42. 	vector<Node> heap;
  43. 	int idx = -1;
  44.  
  45. 	while(true){
  46. 		cin>>val;
  47.  
  48. 		if(val == 'N')
  49. 			break;
  50.  
  51. 		++idx;
  52.  
  53. 		if(position[val-'a'] == -1){
  54. 			position[val-'a'] = heap.size();
  55. 			heap.push_back({idx, 1, val});
  56. 			increaseKey(heap, position, heap.size()-1);
  57. 		}
  58. 		else{
  59. 			++heap[position[val-'a']].cnt;
  60. 			heapify(heap, position, 0, heap.size());
  61. 		}
  62.  
  63. 		if(heap[0].cnt == 1)
  64. 			cout<<"The current non-repeating first character is: "<<heap[0].chr<<"\n";
  65. 		else
  66. 			cout<<"No non-repeating first character available.\n";
  67. 		cout<<"===============================================\n";
  68. 	}
  69.  
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
a a b c c d b d x N
stdout
copy 
The current non-repeating first character is: a
===============================================
No non-repeating first character available.
===============================================
The current non-repeating first character is: b
===============================================
The current non-repeating first character is: b
===============================================
The current non-repeating first character is: b
===============================================
The current non-repeating first character is: b
===============================================
The current non-repeating first character is: d
===============================================
No non-repeating first character available.
===============================================
The current non-repeating first character is: x
===============================================
https://ideone.com/FLzeFU
First no-repeating character in a stream
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!