Coding · Hashing
First Non-Repeating Character in a Stream
- Reported once
- Medium
- senior SDE
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Characters arrive one at a time. After each arrival, report the first character that has appeared exactly once so far, or # if no character is unique, and return all the reports joined into one string. For the stream "mamas" the answer is "mma#s". There are up to 100,000 characters, and each report must be cheap because the stream never stops.
Restated in our own words, not a quote from Myntra or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask what "first" means: the earliest arrival among the characters that are still unique. Which characters can appear: only lowercase letters, or any character? Is the stream given as a whole string, or arriving through a call, and does the caller need the answer after every character? What should be reported when nothing is unique: a marker like #? And how long can the stream be, to know if rescanning is affordable?
Assumptions I would state: any characters are possible, the answer after every character is needed, # means none is unique, and the stream can reach 100,000 characters.
Brute force
Say the obvious answer and why it is too slow.
After each new character, count every character of the prefix seen so far, then scan the prefix from the left and report the first one whose count is 1. Another version keeps a count map but still scans the whole prefix for the first unique character.
Either way, each report costs O(n), so the whole stream costs O(n²). At 100,000 characters that is around five billion steps, too slow, and it also gets worse the longer the stream runs. The scan is wasted work: the answer changes only a little between two steps, yet we rebuild it from scratch every time.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(k) for k distinct characters, plus the output
The pattern is queue plus counts. Keep a count of each character, and keep a queue of the characters in the order of their first arrival. The answer is always the first character in the queue that is still unique.
When a character arrives, add one to its count. If the count is now 1, it is new, so push it at the back of the queue. If it is 2 or more, it is a repeat and it is not pushed again. Then look at the front of the queue: while the front character has a count above 1, it can never be unique again, so drop it. After that, the front, if there is one, is the answer. If the queue is empty, report #.
Why is it correct? A character's count only goes up, so once it is repeated it stays repeated, and dropping it from the front is safe forever. The queue holds characters in the order of first arrival, so the first one that is still unique is the earliest unique character. Characters behind the front that have become repeats are not removed yet, but they are removed the moment they reach the front, and until then they are never reported.
Each character is pushed at most once and dropped at most once, so the total work over the whole stream is linear, which is O(1) per character on average. In JavaScript, do not use shift to drop from a plain array, since that can cost O(n). Move a head index forward instead. Map lookups are O(1) on average.
Out loud: "Counts for repeats, a queue for first-arrival order, and clean the front before answering."
Walk it through
A dry run on the example, step by step.
| Step | Char in | Count of char | Live queue | Report |
|---|---|---|---|---|
| 1 | m | 1 | m | m |
| 2 | a | 1 | m a | m |
| 3 | m | 2 | a | a |
| 4 | a | 2 | (empty) | # |
| 5 | s | 1 | s | s |
Take the stream "mamas". The table shows the live part of the queue (from the head onward) after each step.
The first m is new, so it enters the queue and is reported. The a enters behind it, and m stays in front. The second m raises its count to 2, so m is dropped from the front and a becomes the answer. The second a raises its count to 2 and is dropped too, leaving the queue empty, so the report is #. The s enters the empty queue and is reported. The reports are m, m, a, #, s, giving "mma#s".
The code
Runnable JavaScript, checked against test cases.
function firstNonRepeating(stream) {
const counts = new Map();
const queue = [];
let head = 0;
let output = "";
for (const char of stream) {
const count = (counts.get(char) ?? 0) + 1;
counts.set(char, count);
if (count === 1) queue.push(char);
while (head < queue.length && counts.get(queue[head]) > 1) head++;
output += head < queue.length ? queue[head] : "#";
}
return output;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty stream: there are no steps, so the output is an empty string.
- All different: the front never changes, so every report is the first character.
- All the same: the first report is the character and every later one is #.
- A character repeating many times: it is pushed once only, because the push happens only when the count becomes 1.
- A repeat that is not at the front: its count rises but nothing is dropped until it reaches the front.
- Any characters: spaces, digits and capitals work, since the map does not care.
- Queue growth: the queue holds at most one entry per distinct character.
Follow-ups to expect
Where the interviewer pushes next.
- How would you build this as a class with an add method and a query method that returns the current answer in O(1)?
- How would you do it with a doubly linked list and a map so that a repeated character is removed at once instead of lazily?
- How would you find the first non-repeating character of a plain string, in one pass over the counts and one pass to pick?
- How would the design change if the stream is huge and the distinct characters do not fit in memory?
Where candidates slip
The mistakes this problem punishes.
A common mistake is pushing a character onto the queue every time it arrives, which fills it with repeats and breaks the amount of work.
- Cleaning the queue only once, instead of looping while the front is a repeat.
- Calling array shift in a loop, which can make the whole thing quadratic.
- Forgetting to answer # when the queue runs empty, and returning undefined.
- Reporting the most recent unique character instead of the earliest one.
- Using the queue itself to test for repeats, instead of a count map.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.