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

The problem

Return the index of the first character that appears exactly once. If there is none, return −1.

InputAnswer
"leetcode"0 — l
"loveleetcode"2 — v
"aabb"−1
""−1
"z"0

The naive approach checks each character against the whole string: O(n²). The expected solution is two passes and 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.

Run it

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.

1Python
Output
2Python
Output
3Python
Output

                

                

                    
Two passes

                    
4Python
Output
Pass one counts every character. Pass two walks the string in order and returns the first index whose count is 1.
O(n) time, O(k) space where k is the alphabet size — bounded by 26 for lowercase ASCII, so effectively O(1) for that case.
Why two passes are necessary: the answer depends on the total count of a character, which is not known until the whole string has been read. A single pass cannot decide whether the first character is unique before seeing the end.
Note the second loop iterates the string, not the counter. Iterating the counter would give the first character in insertion order that happens to have count 1, which is the same thing in CPython 3.7+ because dictionaries preserve insertion order — and relying on that is less clear than walking the string.

                

                

                    
The single-pass variant

                    
If asked for one pass over the input, the answer stores indices and resolves at the end:
5Python
Output
Still O(n) overall, and the final scan is over the alphabet rather than the string — so for a long string with a small alphabet it touches less data.
Whether this counts as "one pass" is arguable, and the useful observation to make is that the information required is not available until the input ends, so some second look is unavoidable. Saying that is better than claiming a single-pass solution that does not exist.

                

                

                    
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).

                

                

                    
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.

                

                

                    
The array optimisation

                    
For a known small alphabet, an array replaces the dictionary:
6Python
Output
Faster in practice — array indexing beats hashing — and it breaks on anything outside lowercase ASCII.
Worth offering as the optimised version with the assumption stated. Presenting it without noting that it assumes lowercase ASCII is the mistake; interviewers frequently follow up with "what about Unicode?"
 CounterArray
TimeO(n)O(n)
SpaceO(k)O(26)
AlphabetAnyLowercase ASCII only
Constant factorHigherLower

                

                

                    
Edge cases

                    
CaseResultWhy
Empty string−1The loop does not run
All characters repeat−1No count equals 1
Single character0Count is 1
All unique0The first character qualifies
Mixed case"Aa" gives 0 — different charactersAsk whether case matters
Spaces and punctuationCounted as charactersAsk whether they should be
Non-ASCIIWorks with Counter, breaks with the arrayMention the assumption
The mixed-case row is a legitimate clarifying question: is "Aa" two unique characters or one repeated one?

                

                

                    
The variants

                    
First repeating character. Simpler and genuinely one pass: keep a set of seen characters and return the first one already present.
7Python
Output
That asymmetry is worth noticing: "first repeating" can be answered as soon as the repeat appears, so one pass suffices. "First non-repeating" cannot, because uniqueness is only knowable at the end.
First unique in a stream. A queue of candidates plus a count map: push each new character, and pop from the front while the front's count exceeds 1. The front is always the current answer, in O(1) per query.
Last non-repeating character. Same counts, iterate the string backwards.
First non-repeating word in a document. Identical structure over tokens rather than characters.

                

                

                    
What it is testing

                    
Do you use two passes rather than a nested loop? The O(n²) version is the baseline to improve on.
Do you iterate the string in the second pass? Order matters, and the counter's order is an implementation detail to avoid depending on.
Do you know the alphabet-size bound? Stating the space as O(1) for a fixed alphabet, rather than O(n), is the precise answer.
Do you ask about case and non-letter characters?
Do you notice the asymmetry with "first repeating"? Recognising that one is answerable in a single pass and the other is not shows you understand why the two passes are needed.

                

                

                    
Recap in one screen

                    
  • Count every character, then walk the string in order and return the first index with count 1.
  • O(n) time, O(k) space bounded by the alphabet — effectively O(1) for fixed alphabets.
  • Two passes are unavoidable: uniqueness is not knowable until the input ends.
  • Iterate the string, not the counter, in the second pass.
  • "First repeating" is the one-pass sibling, answerable the moment the repeat appears.

                

            


        

    



How the code works
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.
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