First non-repeating character in a stream
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"
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('');}