First non-repeating character in a stream of characters

• Time : $O(n)$
• Space : $O(1)$

c++

string Solution::solve(string A) {
    deque<char> dq;
    string res = "";
    unordered_map<char, int> freq;
    for(int i = 0; i < A.size(); i++) {
        freq[A[i]]++;
        while(dq.size() and freq[dq.front()] > 1) dq.pop_front();
        if(freq[A[i]] <= 1) dq.push_back(A[i]);
        if(dq.empty()) res.push_back('#');
        else res.push_back(dq.front());
    }
    return res;
}