vizlearn

First non-repeating character

Interview QuestionsBy Updated

Two passes. Count every character, then walk the string again and return the first with a count of one. One pass cannot do it — you cannot know a character is unique until you have seen the whole string. O(n) time, O(k) space.

Overview

Why one pass is impossible

Reading left to right, the first character might be unique or might repeat at the very end. Nothing can be returned until the whole string has been read, so a single pass that emits an answer as it goes is wrong by construction.

What a single pass can do is record enough to answer at the end — which is what the counter is. The second pass is not extra work in the complexity sense: two linear passes is still O(n).

StringsCoding problemEasy

Step through it

What to watch

  • Pass one fills the counter; nothing is decided during it.
  • Pass two returns at the first count of 1 — order comes from the string, not the dictionary.
  • swiss: w wins, because s repeats.

Say this out loud

"Count in one pass, then scan again for the first count of one. Two passes is O(n) - and you can't do it in one, because uniqueness isn't decidable until the end."

First non-repeating character

Find the first character in a string that does not repeat.

Why the second pass walks the string

The answer must be the first such character, and "first" is a property of the string, not of the counter. Walking the string gets the order for free.

Since Python 3.7 dictionaries preserve insertion order, so walking counts.items() also works and touches only distinct characters. Say which guarantee you are relying on — it is a language guarantee since 3.7, and was an implementation detail in 3.6.

The stream variant

The real follow-up: "characters arrive one at a time and you must answer at any moment." Keep a counter and a queue of candidates. On each arrival, push it to the queue, then pop from the front while the front has a count above one. The head of the queue is always the current answer, in O(1) amortised.

Run it in Python

The two-pass version, then the same answer read straight out of the ordered dictionary, then the streaming variant that answers after every single character.

first_unique.pyPython 3
Output
How the code works
  1. counts = Counter(s)The first pass. It decides nothing; it only records enough that the second pass can decide immediately.
  2. for i, ch in enumerate(s):Walking the string, not the counter, because "first" is a property of the string. Iterating the dict works too and relies on insertion order — a language guarantee only since 3.7.
  3. while self.candidates and self.counts[...] > 1:The streaming variant. The queue front is always the answer, and each character is pushed once and popped at most once, so it is O(1) amortised per arrival.
  4. return -1, NoneEvery character repeated. The sentinel has to be something the caller can distinguish from index 0 — the same trap as str.find.
Change one thing
  • Feed the stream "aabbcc" and print after each character. The answer becomes None and stays there.
  • Replace the deque with a list and pop(0). Same answers, and the amortised O(1) is gone.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why can this not be solved in a single pass?
  2. The second pass walks the string rather than the counter because:
  3. In the streaming version, what makes each add O(1) amortised?





 Cheat sheet
First non-repeating character
Two passes. Count every character, then walk the string again and return the first with a count of one. One pass cannot do it — you cannot know a character is unique until you have seen the whole string. O(n) time, O(k) space.
INTERVIEW · vizlearn.in/interview/first-non-repeating-character.html
More in Interview
InterviewValid parenthesesInterviewRun-length string compressionInterviewLongest common prefixInterviewImplement substring search (strStr)
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact