First non-repeating character in a stream

Medium

Problem

Characters arrive one at a time. After each one, report the first character so far that has appeared exactly once, or "#" if there is none.

Example 1

Input:  "aabc"
Output: "a#bb"

After a → a; after aa → #; after aab → b; after aabc → b.

Also asked as: Find the first non-repeating character from a stream of characters · Queue based approach or first non-repeating character in a stream

Test cases

Case 1

Input:    "aabc"
Expected: "a#bb"

Case 2

Input:    "abcabc"
Expected: "aaabc#"

Case 3

Input:    "zz"
Expected: "z#"

Case 4

Input:    "a"
Expected: "a"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Queue of candidates + frequency count

Time O(1) amortised per charSpace O(k)

Push each new char to a queue and bump its count. Before answering, pop from the front while its count > 1. The front (if any) is the current first non-repeating char.

function firstNonRepeatingStream(chars) {
const count = new Map(), queue = [];
const out = [];
for (const c of chars) {
count.set(c, (count.get(c) || 0) + 1);
queue.push(c);
while (queue.length && count.get(queue[0]) > 1) queue.shift();
out.push(queue.length ? queue[0] : '#');
}
return out.join('');
}