#include <iostream>
#include <queue>
 
using namespace std;
 
void first_non_repeating_character(const string& stream) {
 
    // Initializing an array to store the frequency of characters (ASCII range)
    int frequency[128] = {0}; 
    // Initializing a queue to store characters
    queue<char> queue; 
 
    for (char c : stream) {
        int index = static_cast<int>(c); // Converting character to its ASCII value
        frequency[index]++; // Incrementing the frequency of the character
 
        if (frequency[index] == 1) { // If the frequency becomes 1, it's the first occurrence
            queue.push(c); // and hence we enqueue the character into the queue
        }
    }
 
    // Removing characters from the front of the queue until we find a non-repeating character 
    // (i.e., a character with frequency 1) or until the queue is empty
    while (!queue.empty() && frequency[static_cast<int>(queue.front())] > 1) {
        queue.pop(); // Removing characters with frequency greater than 1
    }
 
    // If the queue is not empty, the front element is the first non-repeating character
    // Otherwise, there's no non-repeating character found so far.
    if (!queue.empty()) {
        cout <<"The first non repeating character in the string '"<<stream<<"' is: "<< queue.front() <<endl; // the first non-repeating character
    } else {
        cout <<"There is no non-repeating character in the string: '"<<stream<<"'"<<endl; // if no non-repeating character found
    }
}
 
int main() {
    string stream = "abacabad";
    first_non_repeating_character(stream);
    cout << endl;  
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBmaXJzdF9ub25fcmVwZWF0aW5nX2NoYXJhY3Rlcihjb25zdCBzdHJpbmcmIHN0cmVhbSkgewoKICAgIC8vIEluaXRpYWxpemluZyBhbiBhcnJheSB0byBzdG9yZSB0aGUgZnJlcXVlbmN5IG9mIGNoYXJhY3RlcnMgKEFTQ0lJIHJhbmdlKQogICAgaW50IGZyZXF1ZW5jeVsxMjhdID0gezB9OyAKICAgIC8vIEluaXRpYWxpemluZyBhIHF1ZXVlIHRvIHN0b3JlIGNoYXJhY3RlcnMKICAgIHF1ZXVlPGNoYXI+IHF1ZXVlOyAKCiAgICBmb3IgKGNoYXIgYyA6IHN0cmVhbSkgewogICAgICAgIGludCBpbmRleCA9IHN0YXRpY19jYXN0PGludD4oYyk7IC8vIENvbnZlcnRpbmcgY2hhcmFjdGVyIHRvIGl0cyBBU0NJSSB2YWx1ZQogICAgICAgIGZyZXF1ZW5jeVtpbmRleF0rKzsgLy8gSW5jcmVtZW50aW5nIHRoZSBmcmVxdWVuY3kgb2YgdGhlIGNoYXJhY3RlcgoKICAgICAgICBpZiAoZnJlcXVlbmN5W2luZGV4XSA9PSAxKSB7IC8vIElmIHRoZSBmcmVxdWVuY3kgYmVjb21lcyAxLCBpdCdzIHRoZSBmaXJzdCBvY2N1cnJlbmNlCiAgICAgICAgICAgIHF1ZXVlLnB1c2goYyk7IC8vIGFuZCBoZW5jZSB3ZSBlbnF1ZXVlIHRoZSBjaGFyYWN0ZXIgaW50byB0aGUgcXVldWUKICAgICAgICB9CiAgICB9CiAgICAKICAgIC8vIFJlbW92aW5nIGNoYXJhY3RlcnMgZnJvbSB0aGUgZnJvbnQgb2YgdGhlIHF1ZXVlIHVudGlsIHdlIGZpbmQgYSBub24tcmVwZWF0aW5nIGNoYXJhY3RlciAKICAgIC8vIChpLmUuLCBhIGNoYXJhY3RlciB3aXRoIGZyZXF1ZW5jeSAxKSBvciB1bnRpbCB0aGUgcXVldWUgaXMgZW1wdHkKICAgIHdoaWxlICghcXVldWUuZW1wdHkoKSAmJiBmcmVxdWVuY3lbc3RhdGljX2Nhc3Q8aW50PihxdWV1ZS5mcm9udCgpKV0gPiAxKSB7CiAgICAgICAgcXVldWUucG9wKCk7IC8vIFJlbW92aW5nIGNoYXJhY3RlcnMgd2l0aCBmcmVxdWVuY3kgZ3JlYXRlciB0aGFuIDEKICAgIH0KCiAgICAvLyBJZiB0aGUgcXVldWUgaXMgbm90IGVtcHR5LCB0aGUgZnJvbnQgZWxlbWVudCBpcyB0aGUgZmlyc3Qgbm9uLXJlcGVhdGluZyBjaGFyYWN0ZXIKICAgIC8vIE90aGVyd2lzZSwgdGhlcmUncyBubyBub24tcmVwZWF0aW5nIGNoYXJhY3RlciBmb3VuZCBzbyBmYXIuCiAgICBpZiAoIXF1ZXVlLmVtcHR5KCkpIHsKICAgICAgICBjb3V0IDw8IlRoZSBmaXJzdCBub24gcmVwZWF0aW5nIGNoYXJhY3RlciBpbiB0aGUgc3RyaW5nICciPDxzdHJlYW08PCInIGlzOiAiPDwgcXVldWUuZnJvbnQoKSA8PGVuZGw7IC8vIHRoZSBmaXJzdCBub24tcmVwZWF0aW5nIGNoYXJhY3RlcgogICAgfSBlbHNlIHsKICAgICAgICBjb3V0IDw8IlRoZXJlIGlzIG5vIG5vbi1yZXBlYXRpbmcgY2hhcmFjdGVyIGluIHRoZSBzdHJpbmc6ICciPDxzdHJlYW08PCInIjw8ZW5kbDsgLy8gaWYgbm8gbm9uLXJlcGVhdGluZyBjaGFyYWN0ZXIgZm91bmQKICAgIH0KfQoKaW50IG1haW4oKSB7CiAgICBzdHJpbmcgc3RyZWFtID0gImFiYWNhYmFkIjsKICAgIGZpcnN0X25vbl9yZXBlYXRpbmdfY2hhcmFjdGVyKHN0cmVhbSk7CiAgICBjb3V0IDw8IGVuZGw7ICAKICAgIAogICAgcmV0dXJuIDA7Cn0=