First Unique in a Stream
Module 9 · Queues
Problem
Characters arrive one at a time from a stream. After each arrival,
report the first character (in arrival order) that has appeared exactly
once so far — or # if none exists.
Examples
Example 1
Input
add("a")Output"a"Example 2
Input
add("b")Output"a"Example 3
Input
add("a")Output"b"Explanation. a now has count 2, so first unique is b
Example 4
Input
add("b")Output"#"Explanation. nothing unique
Example 5
Input
add("c")Output"c"Example 6
Input
add("b")Output"c"Constraints
≤ 10⁵ arrivals · lowercase letters.
Attempt it first
Module 6's First Unique Character ended with this exact variant as "Module 9 material" — the promised follow-up. There, you could re-scan the string per query: O(n) per report, O(n²) for the stream. The challenge: amortized O(1) per arrival. The Count verb still provides half the answer; the new half is what this module adds.