~/problems / Arrays & hashing / Hash maps and counting

Basics: count with a dict, then look up

easy basics ~10 min

Write first_unique(s: str) -> int that returns the index of the first character in s that occurs exactly once in the whole string, or -1 if every character repeats.

first_unique("swiss")    # 1   ('w'; 's' repeats, and 'i' comes later)
first_unique("abab")     # -1
first_unique("z")        # 0
  • 0 <= len(s) <= 10^5; s can contain any characters, and upper and lower case are different characters.
  • Calling s.count(ch) for each position is O(n²) in general. Do it in two passes instead: count, then scan.
Show hint

first build a dict (or collections.Counter) from character to how many times it appears, then walk s again and return the first index whose count is 1.

Topic: Hash maps and counting. Counter/defaultdict, complement lookups, prefix-sum + hash map.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc