2Brute2Best
🔥0

Remove All Adjacent Duplicates In String

Easy·LeetCode #1047 Pro OnlyBasic Reinforcement
LeetCode
01

Problem Statement

You are given a string s of lowercase letters.

One move is: pick two equal letters that sit next to each other and delete both. Keep making moves until no two neighbours are equal.

Return the final string. It can be shown that the result is the same no matter which pairs you delete first.

Input

A string s of lowercase English letters.

Output

The string left after all possible deletions (it may be empty).

Example 1
Input: s = "abbaca"
Output: "ca"

Delete "bb" to get "aaca". Now the two a's are neighbours, so delete "aa" to get "ca". No equal neighbours are left.

Example 2
Input: s = "azxxzy"
Output: "ay"

Delete "xx" → "azzy", then delete "zz" → "ay".

Constraints
  • • 1 ≤ s.length ≤ 10^5
  • • s contains only lowercase English letters
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“two adjacent equal letters”
→ A pair forms between a letter and the one right before it → compare with the latest survivor.
“repeatedly, until no more”
→ Deletions can chain. A stack handles chains automatically, because after a pop the next letter faces the new top.
“return the final string”
→ The survivors in order are the answer, so the stack can be the answer string itself.
03

Approach Complexity Ladder

Brute Force — delete the first pair, start overO(N²)O(1)

Find the first pair of equal neighbours, delete it, rescan from the start

Optimal — the answer string is the stackO(N)O(N)

push_back each letter; if it equals back(), pop_back instead

Brute Force Intuition

Do exactly what the statement says. Scan for the first place where s[i] == s[i+1], erase those two letters, and scan again from the beginning. Stop when a full scan finds no pair.

Recognition rule for this sub-pattern:

Opening things wait on the stack until their closing partner arrives.
Remember this · Stack
Trigger
Matching pairs, nested structure, undo, evaluating expressions, "the last one wins".
Think
Does each new element need to look at the most recent unresolved element?
Key question
What does an item on the stack represent, and when does it get resolved?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Expression Parser & Interpreter Pattern

Abstract syntax tree evaluation and operator precedence parsing.

Explore Track
C++ Internals

Stack vs Heap Segments

Call stack frame layout, return addresses, and buffer overflow prevention.

Explore Track
Valid ParenthesesMinimum Remove to Make Valid Parentheses