The first one that has not repeated
After each letter of a stream, report the earliest letter that has appeared exactly once, using a queue of candidates and a count per letter. About 14 minutes.
Candidates in arrival order
Letters arrive one at a time. After each one, you need the earliest letter that has appeared only once so far. Keep a count for each letter, and a queue of letters that have appeared exactly once, oldest at the front.
A new letter is added to the queue only the first time it is seen. When it comes again, its count goes up.
q = deque()
q.append("Asha")
q.append("Ben")
served = q.popleft() # Ashax arrives and joins the queue. The answer is x.
Clean the front
A letter that repeated may be in the queue, but it no longer qualifies. Before answering, drop letters from the front while the front letter has a count above one.
Then the front, if there is one, is the earliest letter seen exactly once. If the queue is empty, no letter qualifies, so the answer for that moment is a hash sign. Letters in the middle are never examined until they reach the front.
front = q[0] if q else None # peek without removing
A letter repeats while it is in the middle of the queue. What do you do?
- ALeave it there, and drop it when it reaches the front
- BSearch the queue and remove it at once
- CKeep it as the answer
Show the answer
Leave it there, and drop it when it reaches the front. Only the front is ever used for an answer, so the dead letter can wait.
First unique letter so far
You are given a string s of lowercase letters that arrive one at a time. After each letter, find the first letter in the string so far that has appeared exactly once. Return a string of the same length whose characters are those letters, using # when there is none.
s = "aabcbd" → "a#bbcc"
0 ≤ length of s ≤ 100,000 · s has only lowercase letters