First order code that appears only once

Arrays, strings and hash maps Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from collections import Counter
s = "abacabad"
c = Counter(s)
print(next((i for i, ch in enumerate(s)
            if c[ch] == 1), -1))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3

Right: 'c' at index 3 is the first letter with a count of 1.

Counts are a: 4, b: 2, c: 1, d: 1; the scan over the string meets 'c' first.

Why not the others?
  • B 7. 'd' also appears once, but later than 'c'.
  • C 1. 'b' appears twice, at indexes 1 and 5.

30-second answer

Count every letter in one pass, then scan again and return the first index whose count is 1. Two linear passes: O(n) time, and O(1) extra space because the alphabet has 26 letters. A nested scan per letter would be O(n²).

Practise saying it · 30 s. No recording, just a timer

Explain the two-pass approach for the first unique letter.

Say your answer out loud, then check which of these points you covered:

  • Count first
  • Scan the string in order
  • O(n) time, alphabet-bounded space

Deep dive

Counting first is necessary: you cannot know a letter is unique until you have seen the whole string.

The second pass walks the string, not the counts, so 'first' means first in the original order.

Counter is fine in an interview; say that its memory is bounded by the alphabet, not by n.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def first_single(codes: str) -> int:
    counts: dict[str, int] = {}
    for ch in codes:
        counts[ch] = counts.get(ch, 0) + 1
    for i, ch in enumerate(codes):
        if counts[ch] == 1:
            return i
    return -1

Common mistakes

  • Scanning the counter's keys for the first count of 1, which relies on insertion order and returns a letter instead of an index.
  • Calling s.count(ch) inside the loop, which is O(n) per call.

Senior take & follow-ups

Two passes beat clever single-pass tricks for clarity. Say why the second pass is over the string.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if letters stream in and you must answer after each one?

    Show hint

    Keep counts plus a queue of candidates; pop from the front while the front's count exceeds 1.

  2. What if the alphabet is all of Unicode?

    Show hint

    Same idea with a dict; space becomes O(distinct characters).

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.