Skip to content

Volume ITechnology

4.0.13 — First Non-Repeating Character, and Removing Duplicates ​

Classic · Easy · LeetCode 387 (First Unique Character), LeetCode 1047 (Remove Adjacent Duplicates)

The problem ​

  1. Find the first character that appears only once. In "swiss", that is w.
  2. Find the first character that appears a second time. In "swiss", that is s, at position 3.
  3. Remove repeated characters, keeping the first of each. "programming" becomes "progamin".
  4. Remove pairs of equal neighbours again and again. "abbaca" becomes "ca".

1. First non-repeating character ​

The slow way, and what it wastes ​

For each character, count how many times it appears in the whole string. Return the first with a count of 1. That is a loop inside a loop, O(n^2). The waste is plain: the count for s is worked out again every time an s appears.

Two passes with a counter ​

Count everything once. Then walk the string a second time and return the first character whose count is 1.

python
def first_unique(s: str) -> int:
    freq = {}
    for ch in s:                       # (1) pass 1: count
        freq[ch] = freq.get(ch, 0) + 1
    for i, ch in enumerate(s):         # (2) pass 2: find
        if freq[ch] == 1:
            return i
    return -1                          # (3)

print(first_unique("swiss"))      # → 1
print(first_unique("leetcode"))   # → 0
print(first_unique("aabb"))       # → -1

(1) After this loop, freq knows the final count of every character.

(2) Walk in the original order. The first character with count 1 is the answer. enumerate gives both the position i and the character.

(3) No character is unique.

Why two passes, not one? While you are still counting, you cannot know whether a character will appear again later. In "swiss", the first s looks unique until you reach position 3. Only after the whole string has been seen are the counts final.

Why walk the string in pass 2, not the dictionary? We want the first in the string. Dictionaries remember the order keys were added, so walking freq would also work here. But walking s makes the intent obvious and does not depend on that dictionary rule.

2. First repeating character ​

This one can be done in one pass. The moment you see a character you have seen before, it is the answer. Nothing later can come first.

python
def first_repeat(s: str) -> str | None:
    seen = set()
    for ch in s:
        if ch in seen:      # (1)
            return ch
        seen.add(ch)
    return None

print(first_repeat("swiss"))     # → s
print(first_repeat("abcdef"))    # → None

(1) Check before you add. Adding first would make every character look like a repeat of itself.

"First repeating" has two meanings, so ask which one is meant. This code finds the character whose second appearance comes first. In "abba" that is b, because the second b (position 2) comes before the second a (position 3). The other meaning is the character whose first appearance is earliest among those that repeat, which would be a. That one needs the two-pass counter.

3. Remove duplicate characters, keep the first of each ​

python
def remove_duplicates(s: str) -> str:
    seen = set()
    out = []
    for ch in s:
        if ch not in seen:
            seen.add(ch)
            out.append(ch)      # keep only the first appearance
    return "".join(out)

print(remove_duplicates("programming"))   # → progamin

The set answers "have I kept this already?" in one step. The list keeps the order. A set alone would lose the order, so "".join(set(s)) gives the right letters in a random order. That is a common wrong answer.

Python has a one-line version that keeps order:

python
print("".join(dict.fromkeys("programming")))   # → progamin

dict.fromkeys makes a dictionary whose keys are the characters. A key can appear only once, and dictionaries keep the order keys were first added. So the keys are exactly the first appearances, in order.

4. Remove adjacent duplicates, again and again ​

Remove any two equal neighbours. Removing a pair can bring two new equal letters together, so keep going until no pair is left.

abbaca  →  remove "bb"  →  aaca  →  remove "aa"  →  ca

The slow way ​

Scan for a pair, remove it, rebuild the string, and start again from the beginning. Each scan is O(n). You might need n/2 removals. So it is O(n^2).

The stack idea ​

A stack is a pile where you can only add to the top or take from the top. A Python list works as one: append adds to the top, pop removes from the top, and stack[-1] looks at the top.

Read the characters one at a time. Keep the characters that have survived so far on the stack. For each new character:

  • If it equals the top of the stack, the two cancel. Pop the top and do not push the new one.
  • Otherwise, push the new character.

Why does this work? The top of the stack is always the character just before the current one in the reduced string. When a pair cancels, the character below it becomes the new top. That is exactly the letter that now sits next to whatever comes next. So a chain of cancellations happens naturally, with no rescanning.

python
def remove_adjacent(s: str) -> str:
    stack = []
    for ch in s:
        if stack and stack[-1] == ch:   # (1)
            stack.pop()                 # (2)
        else:
            stack.append(ch)            # (3)
    return "".join(stack)

print(remove_adjacent("abbaca"))   # → ca
print(remove_adjacent("azxxzy"))   # → ay

(1) The stack must not be empty, and its top must equal the new character.

(2) They cancel. The pair disappears.

(3) No match. This character survives for now.

Trace on "abbaca":

charactionstack after
apusha
bpusha b
bequals top, popa
aequals top, pop(empty)
cpushc
apushc a

The answer is "ca". Each character is pushed at most once and popped at most once, so the total work is O(n). The stack gets its full chapter in 4.8.0, where the same "match with the top" idea checks brackets.

Complexity ​

TaskTimeExtra memory
First uniqueO(n)O(k)
First repeatO(n)O(k)
Remove duplicatesO(n)O(n)
Remove adjacent pairsO(n)O(n)

Here k is the number of distinct characters. For lowercase letters it is at most 26.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Why can't you find the first unique character in one pass?" While you are still reading, a character may appear again later. In "swiss", the first s looks unique until position 3. So count everything first, then look for the first count of 1.

"Remove duplicate characters but keep the order." Use a set to remember what you have kept, and a list to keep the order. A set alone would lose the order. "".join(dict.fromkeys(s)) also works in one line.

"Remove pairs of equal neighbours in one pass." Use a stack. If the new character matches the top of the stack, pop the top. If not, push the new character. When a pair is removed, the character below becomes the new top, so chains like "abba" also disappear.

"What if the characters arrive one by one and you cannot store them all?" Keep a count for each character and a queue of characters seen once. When a character's count goes above 1, drop it from the front of the queue. The front of the queue is always the first unique character so far.

One thing to volunteer: "The stack works because removing a pair brings the next two neighbours together, and the stack's top is exactly that neighbour."

Next: 4.0.14 String Rotation, Compression and Longest Common Prefix. Three classic tricks, one of them a single line.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet