AI Hints
Home›DSA in Python Tutorial›Sets and Hashing Practice
DSA in Python · Lesson 24 of 132

Practice: First Unique

Count, then search.

⏱ 2 min read▶ Video at 27:29🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Find the first character in a word that appears only once. In swiss, it's W. Pause and try. Hint. You might need to go through the word twice.

Practice: First Unique
From the video: Practice: First Unique
  • The first character that appears once
  • In 'swiss', it's w
  • Two passes?

First pass, count every character with Counter. Second pass, go through the word in order, and return the first character with a count of one. Two passes is still O of N, because two N is just O of N. Run it. W for swiss, V for level, and none for AABB, where nothing is unique.

first_unique.pypython
from collections import Counter

def first_unique(word):
    counts = Counter(word)
    for ch in word:
        if counts[ch] == 1:
            return ch
    return None

for w in ["swiss", "level", "aabb"]:
    print(w, "->", first_unique(w))
Output
swiss -> w
level -> v
aabb -> None

The counting pattern

Many problems follow this same shape. Count things with a dictionary in one pass, then use the counts in a second pass. Most frequent word, first unique item, checking for anagrams, and finding duplicates all work this way.

keyvalue
Pass 1count with Counter
Pass 2use the counts
Totalstill O(n)
Used foruniques, anagrams, top k

Summary

Count in one pass, then search in a second. It's simple, fast, and works for many problems. Next, a technique for scanning ranges of an array. The sliding window.

Key takeaways
  • Counter first
  • Then scan in order
  • O(n)
Next up: Sliding Window — a moving range