Introduction

The Remove Adjacent Duplicates problem involves removing neighboring duplicate characters from a string.

The task is to:

  • repeatedly remove adjacent duplicates
  • return the final remaining string

Example:

Input:"abbaca"

Output:
"ca"

Explanation:

abbaca
Remove "bb":
aaca

Remove "aa":
ca

This problem is one of the most important applications of:

Stack Data Structure

Constraints

1 <= s.length <= 10^5
String contains:
lowercase English letters

Approach 1 : Brute Force (Repeated String Traversal)

Explanations:

Explanation:

The idea is:

  • repeatedly traverse string
  • remove adjacent duplicates
  • continue until no duplicates remain

Steps:

  1. Traverse string.
  2. Detect adjacent duplicates.
  3. Remove duplicates.
  4. Repeat traversal.

This approach becomes inefficient because:

  • string rebuilding happens multiple times
  • repeated traversals increase complexity

So stack-based solution is preferred.

Dry Run

Input:abbaca

Step 1:
Remove "bb"

String:
aaca

Step 2:
Remove "aa"

String:
ca

Final Output:
ca

Practice :


Complexity Analysis :

Time Complexity:-O(n²) Explanation :
String may be traversed multiple times

Space Complexity:- O(n)
Explanation :
Extra temporary string is used.

Approach 2 : Optimal Solution(Using Stack)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • use stack to track characters
  • if current character matches top:
    • remove duplicate
  • otherwise:
    • push character

At the end:

  • stack contains final string

This efficiently removes adjacent duplicates in one traversal.

Dry Run

Input:abbaca

Step 1:
Push a

Stack:
[a]

Step 2:
Push b

Stack:
[a, b]

Step 3:
Current b matches top
Pop b

Stack:
[a]

Step 4:
Push a

Stack:
[a, a]

Step 5:
Current a matches top
Pop a

Stack:
[]

Step 6:
Push c
Push a

Final Stack:
[c, a]

Final Output:
ca

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Each character is processed only once.

Space Complexity:- O(n)
Explanation :
Stack stores characters.

Why This Problem is Important

This problem builds the foundation for:

  • Stack operations
  • String processing
  • Duplicate handling
  • Pattern matching
  • Character traversal techniques

Real-World Applications

Adjacent duplicate removal is used in:

  • Text editors
  • String compression
  • Data cleanup systems
  • Pattern filtering
  • Compiler preprocessing

Common Beginner Mistakes

  • Forgetting repeated removals
  • Incorrect stack condition
  • Wrong output construction
  • Ignoring empty stack checks
  • Using inefficient string operations

Interview Tip

Interviewers often expect:

  • proper stack usage
  • O(n) optimization
  • clean traversal logic
  • duplicate handling explanation

Always explain:

  • why stack helps track adjacent characters
  • how popping removes duplicates instantly

Related Questions

  • Valid Parentheses
  • Decode String
  • Simplify Path
  • Backspace String Compare
  • Make String Great

Final Takeaway

The Remove Adjacent Duplicates problem is one of the most important stack + string problems.

It teaches:

  • stack processing
  • duplicate elimination
  • string traversal
  • efficient character handling

Understanding this problem builds a strong foundation for:

  •  stack interview problems
  • advanced string processing
  • pattern matching algorithms.