289. First Non-Repeating Character in a Stream

Characters arrive one at a time, appended to a stream. After each new character arrives, print the first character in the stream so far that has appeared exactly once (in the order it originally appeared), or -1 if every character seen so far has repeated. Print one result per character, space-separated, in the order they arrived.

Input: The input is a single line containing the stream, a string of lowercase letters arriving in order. Output: Print one token per character of the stream, space-separated, on one line - the first non-repeating character after each arrival, or -1 if none.

1 <= |stream| <= 10^5, stream consists of lowercase English letters

Once a character is disqualified (its count exceeds 1), it NEVER becomes un-disqualified later - counts only ever increase in this problem, which is exactly why it's safe to permanently discard a disqualified candidate from the front of the queue.

Characters arrive one at a time. After each new arrival, report the earliest character seen so far that has appeared EXACTLY once - or say there isn't one. Brute force: After each new character, re-scan the ENTIRE stream so far looking for the first character with count exactly 1 - this costs O(n) work per character, giving O(n²) overall, which is slow for long streams. Optimised: Instead of re-scanning everything after each new arrival, maintain a queue of 'candidates that MIGHT still be the answer', trimming disqualified ones (count > 1) from the FRONT only as needed - since each character is added to and removed from this queue at most once across the entire stream, the total work stays proportional to the stream's length, not its length squared.

Maintain a 26-entry frequency array and a simple FIFO queue of candidate characters in first-appearance order. On each new character, increment its frequency and enqueue it only if this is its first appearance; then, before reporting the answer, repeatedly dequeue from the front while the front character's frequency is greater than 1, and the answer is whatever remains at the front, or -1 if the queue empties. Since each character is enqueued once and dequeued at most once over the whole stream, the total work across all queries is linear, amortized to O(1) per character. Time: O(n) Space: O(n)

After each new character is appended, re-scan the entire stream built so far from the beginning, computing a fresh frequency count (a 26-entry array suffices for lowercase letters) for that prefix, and return the first character in stream order whose count is exactly 1, or -1 if none exists. Because a full rescan and recount happens after every single character, the total work grows with the square of the stream length. Time: O(n^2) Space: O(1) auxiliary

Maintain a 26-entry frequency array and a min-heap keyed by each character's first-occurrence index, pushing a character onto the heap only the first time it is seen. Before answering each query, peek the heap's minimum and pop away any entries whose character frequency has already risen above 1, since they can never be the answer again, until the heap is empty (answer -1) or its top is genuinely non-repeating (that is the answer). Each heap operation costs logarithmic time, adding an extra factor over the ideal. Time: O(n log n) Space: O(n)

1. Keep a running frequency count for every character seen so far, plus a queue of 'still possibly unique' candidates in the order they first appeared. 2. When a new character arrives, increase its count and add it to the candidate queue. 3. Then repeatedly check the FRONT of the queue: if its count is now more than 1, it's disqualified - remove it and check the new front, repeating as needed. 4. Once the front of the queue genuinely has a count of exactly 1 (or the queue is empty), that's your answer for this step.

Time: O(n) overall, even though it might look like there's a nested loop (the 'while front is disqualified, remove it' step) - each character is only ever removed from the queue once across the whole process, so the total work across all removals is bounded by n, not n per character. Space: O(alphabet size) for the frequency counts, plus O(n) in the worst case for the candidate queue.

a single-character stream (always non-repeating); a stream where every character repeats immediately, giving all -1s; |stream| = 10^5 for performance.

Be ready to justify why this is O(n) overall despite the inner while-loop - this exact 'amortized analysis' argument (each element is removed at most once, ever, across the whole run) is a common follow-up question interviewers ask to test real understanding, not just working code.