186. First Non-Repeating in a Stream
Challenge1000 ms256 MBSolved by 0%
Characters arrive one at a time. After each arrival, report the FIRST character
so far that has appeared exactly once, or # if every character seen so far has repeated.
For aabc the answers are a, then #, then b, then b.
Rescanning everything after each arrival is quadratic. A queue of candidates, in arrival order, makes it one pass.
Constraints - The line has between 1 and 100000 characters. - Lowercase letters only.
Input
A single line of lowercase letters, in arrival order.
Output
Print one line with no spaces: the answer after each arrival, in order.
Use # where no character has appeared exactly once. The output has exactly as many characters as the input.
Inputaabc
Outputa#bb
Noteis the worked example, where the answer becomes # and then recovers
Inputaabb
Outputa#b#
Noteends with everything repeated
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.