Introduction

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

Given a string s, the task is to:

  • repeatedly remove adjacent duplicate characters
  • until no duplicates remain

This problem is an important application of:

 Stack Data Structure

This problem helps in understanding:

  • stacks
  • string processing
  • duplicate removal
  • traversal techniques

Example

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

Explanation:
Remove:
bb

String becomes:
"aaca"

Remove:
aa

Final string:
"ca"

Input:
s = "azxxzy"

Output:
"ay"

Explanation:
Remove:
xx

String becomes:
"azzy"

Remove:
zz

Final string:
"ay"

Constraints

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

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Traverse string repeatedly
  2. Remove adjacent duplicates
  3. Continue until no duplicates remain

This approach works but repeated string rebuilding increases time complexity.

Steps

  1. Traverse string.
  2. Detect adjacent duplicates.
  3. Remove duplicate pair.
  4. Restart traversal.
  5. Continue until no duplicates remain.

Dry Run

Input:s = "abbaca"
Check:
bb
Remove duplicates

String becomes:
"aaca"

Check:
aa
Remove duplicates

String becomes:
"ca"
No duplicates remain

Final Result:
"ca"

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:Repeated traversal and rebuilding of string is performed.

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

Approach 2 : Optimized Solution (Stack)

Explanation

The optimized solution uses a Stack.

The idea is:

  1. Traverse characters one by one
  2. Compare current character
    with stack top
  3. If same:
    • remove duplicate
  4. Otherwise:
    • push character

This efficiently removes adjacent duplicates in one traversal.

Steps

  1. Create empty stack.
  2. Traverse string characters.
  3. Compare with stack top.
  4. Remove duplicates if same.
  5. Otherwise push character.
  6. Build final string.

Dry Run

Input:s = "abbaca"

Traverse a:
Push into stack

Stack:
a

Traverse b:
Push into stack

Stack:
a b

Traverse b:
Duplicate found

Pop b

Stack:
a

Traverse a:
Duplicate found

Pop a

Stack:
empty

Continue traversal...

Final Result:
"ca"

Optimized Code

Complexity Analysis

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

Space Complexity: O(n)
Explanation:
Extra stack is used.

Edge Cases

  1. Empty string
  2. All characters same
  3. No duplicates present
  4. Multiple consecutive duplicates
  5. String length = 1

Why This Problem is Important

This problem helps in understanding:

  1. Stack data structure
  2. Duplicate removal logic
  3. Sequential traversal
  4. String processing
  5. Efficient matching

It is one of the most important stack interview problems.

Real-World Applications

Duplicate-removal concepts are used in:

  1. Text editors
  2. Data cleaning systems
  3. Compiler optimization
  4. Log processing
  5. Compression algorithms

Common Mistakes

  1. Forgetting repeated removals
  2. Incorrect stack conditions
  3. Wrong final string construction
  4. Missing empty stack checks

Interview Tips

Interviewers often expect:

  1. Stack-based optimization
  2. O(n) solution explanation
  3. Proper duplicate handling

Always explain why:

  • stack top represents previous character
  • duplicates are removed immediately

Related Questions

  1. Valid Parentheses
  2. Min Stack
  3. Daily Temperatures
  4. Next Greater Element
  5. Backspace String Compare

Final Takeaway

The Remove Adjacent Duplicates problem is a fundamental stack problem that teaches efficient duplicate elimination and sequential processing techniques. Understanding this problem builds a strong foundation for advanced stack and string-processing interview problems.