first-non-repeating-character-in-a-stream.md

First non-repeating character in a stream

Given an input stream of A of n characters consisting only of lower case alphabets. The task is to find the first non repeating character, each time a character is inserted to the stream. If there is no such character then append '#' to the answer.

Sample Input

zzabbc

Sample Output

z#aaaa

Solution

class Solution {
	public:
    string FirstNonRepeating(string A){

        // non repeating characters queue
        queue<char> nrcq;
        vector<int> used(26, false);

        string ans = "";

        for(int i = 0; i < A.size(); ++i) {
            char c = A[i];
            char output;
            
            if(used[c - 'a'] < 1) {
                nrcq.push(c);
            }
            ++used[c - 'a'];

            while(!nrcq.empty() && used[nrcq.front() - 'a'] > 1) {
                nrcq.pop();
            }

            if(nrcq.empty()) {
                output = '#';
            }
            else {
                output = nrcq.front();
            }
            ans += output;
        }
        return ans;
    }
};

Accepted