[InterviewBit] First non-repeating character in a stream of characters

First non-repeating character in a stream of characters

  • Time :
  • Space :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/10/26/PS/interviewbit/first-non-repeating-character-in-a-stream-of-characters/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.