The first letter that has appeared only once, so far

Letters arrive one at a time. After each one, report the first letter so far that has appeared exactly once. If every letter so far has been repeated, report #.

Worked example#

For a a b c:

So the answer is a # b b.

The idea#

Two words in the question do the work: first, and so far.

"So far" means you cannot look ahead. Each answer has to be right using only what has arrived, which rules out counting everything first and then scanning.

"First" means order of arrival matters, so you need something that remembers the order things came in. That is a queue.

Keep two things:

• a count of how many times each letter has arrived;
• a queue of letters that were unique when they arrived, in arrival order.

When a letter arrives, count it and put it on the back. Then look at the front: if that letter's count has gone above one, it is no longer unique and can be dropped, for ever. Keep dropping until the front is a letter with a count of one, and that is the answer. An empty queue means #.

Why a queue and not a stack#

The answer is the earliest still-unique letter, not the most recent. That is the entire difference, and it is worth holding onto: the same problem asking for the most recent would be a stack, and the same problem asking for the largest would be a heap. The question picks the structure.

Why dropping is safe#

Once a letter has arrived twice, it can never be unique again: counts only go up. So anything dropped from the front is gone for good, and every letter is added once and removed at most once. One pass.

Constraints#

• 1 <= n <= 100000
• Lowercase letters only

About the input#

The letters are written as a count, then that many single-letter words.