267. Find the First Non-Repeating Character From a Stream of Characters

A stream of n lowercase letters arrives one character at a time. After each character is appended to the stream, print the first character (reading the stream so far from the beginning) that has appeared exactly once so far, or -1 if every character seen so far has a duplicate. Print all n answers on a single line, separated by spaces.

Input: The first line contains an integer n, the stream's length. The second line contains a string of n lowercase letters, the stream in arrival order. Output: Print n space-separated tokens on one line - the first non-repeating character after each new arrival, or -1 if every character seen so far repeats.

1 <= n <= 10^5

This is one of the clearest real-world illustrations of WHY a doubly linked list's O(1) middle-deletion matters - a problem that looks like it's about strings/streams turns out to be fundamentally a linked-list data-structure choice problem.

As characters arrive one at a time in a stream, after each one, report the first character seen so far that hasn't repeated yet. Brute force: After every new character, re-scan the ENTIRE stream so far looking for the first character with a count of exactly 1 - this costs O(n) per character, giving O(n²) total, too slow for a long stream. Optimised: A doubly linked list is essential here specifically because it supports O(1) DELETION FROM THE MIDDLE (unlinking a character the moment it repeats) - an array alone couldn't remove a middle element in O(1), which is exactly why this problem is grouped under linked-list techniques rather than simpler array/queue ones.

Maintain a fixed-size frequency array (26 lowercase letters) updated in O(1) as each character arrives, so counts no longer need recomputing from scratch. However, to find the first non-repeating character, still scan the stream prefix built so far from the beginning looking for the first character whose count is 1. This removes the wasted recount of frequencies from the brute approach, but the search for 'the first' non-repeating character still costs a fresh linear scan on every step. Time: O(n^2) Space: O(n)

After each new character is appended, recompute frequency counts from scratch by scanning the entire stream so far, then scan again from the beginning to find the first character whose count is exactly 1. This is correct because it directly reflects the current state of the stream at every step, but redoing a full scan (or two) after every single character makes the total work grow quadratically with the stream length. Time: O(n^2) Space: O(1)

Keep the frequency array plus a queue holding characters in the order they first became candidates: when a new character arrives, increment its count and enqueue it if this is its first occurrence, then repeatedly dequeue from the front while that front character's count has risen above 1. The current front of the queue (if any) is always the first non-repeating character. Since every character is enqueued once and dequeued at most once over the whole stream, the total work across all n steps is linear, even though each individual answer is produced in amortised constant time. Time: O(n) Space: O(n)

1. Maintain a doubly linked list of 'currently non-repeating' characters, in the order they first appeared, alongside a frequency count for every possible letter. 2. When a new character arrives, append it to the DLL; if this character has now been seen MORE than once (its count crosses from 1 to 2), unlink it from the DLL entirely. 3. The FRONT of the DLL is always the current answer - the earliest character that still hasn't repeated - or -1 if the DLL is empty.

Time: O(n) amortized total - each character is appended once and unlinked at most once across the whole stream. Space: O(alphabet size) for the frequency counts, plus O(number of currently-non-repeating characters) for the DLL.

n = 1 (a single character, always non-repeating); a stream where every character is the same letter (only the first position isn't -1); n = 10^5 for performance.

Be ready to explain explicitly WHY a doubly linked list (not a plain queue or array) is the right structure - the need to delete from the MIDDLE of the 'still unique' sequence in O(1), the moment any character repeats, is what a DLL uniquely provides.