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
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution