1047. Remove All Adjacent Duplicates In String - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given a string s, perform duplicate removals repeatedly. In each duplicate removal, choose two adjacent and equal letters and remove them. Continue removing until no more adjacent duplicates remain. It is guaranteed that the final answer is unique.

Examples:

Example 1:
- Input: s = "abbaca"
- Output: "ca"
- Explanation:
  - Remove "bb" → "aaca"
  - Remove "aa" → "ca"
Example 2:
- Input: s = "azxxzy"
- Output: "ay"
- Explanation:
  - Remove "xx" → "azzy"
  - Remove "zz" → "ay"
Example 3:
- Input: s = "aabbcc"
- Output: ""
- Explanation:
  - Remove "aa" → "bbcc"
  - Remove "bb" → "cc"
  - Remove "cc" → ""

Constraints:

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

Hints Before You Start

Hint 1: Consider how you can process the string character by character and remove adjacent duplicates in one pass.
Hint 2: Think about using a stack data structure to efficiently compare the current character with the previously seen one.

Approaches

Brute Force Approach

Idea:

Repeatedly traverse the string.
In each traversal, scan through the string and remove any pair of adjacent duplicate characters.
Continue until you can traverse the string without finding any duplicates to remove.

Steps:

Loop over the string and check adjacent pairs.
When a duplicate pair is found, remove them from the string.
Restart the scanning process until no more removals can be made.

Complexity Analysis:

Time Complexity: O(n²) in the worst-case scenario because you might need to scan the entire string repeatedly after each removal.
Space Complexity: O(n) for storing a new string at each removal step.

Visual Example:

For s = "abbaca":

Iteration 1:
- Scan: "a | bb | aca"
- Remove "bb" → Result: "aaca"
Iteration 2:
- Scan: "aa | ca"
- Remove "aa" → Result: "ca"
No further adjacent duplicates remain.

Python Code (Brute Force):

Python3

. . . .

Java Code (Brute Force):

Java

. . . .

Optimal Approach (Using a Stack)

Idea:

Utilize a stack to process the string in a single pass.
Traverse the string character by character:
- If the stack is not empty and the current character equals the top of the stack, pop the stack (removing the duplicate).
- Otherwise, push the current character onto the stack.
The final stack will contain the string with all adjacent duplicates removed.

Steps:

Initialize an empty stack.
For each character in the string:
- If the stack is non-empty and the top equals the current character, pop the stack.
- Else, push the current character.
Convert the stack back into a string.

Complexity Analysis:

Time Complexity: O(n) because each character is processed exactly once.
Space Complexity: O(n) for the stack in the worst case.

Visual Example:

For s = "abbaca":

Step 1: Stack is empty; push 'a' → Stack: [a]
Step 2: Next character 'b' → Top of stack is 'a' (different), push 'b' → Stack: [a, b]
Step 3: Next character 'b' → Top of stack is 'b' (same), pop → Stack: [a]
Step 4: Next character 'a' → Top of stack is 'a' (same), pop → Stack: []
Step 5: Next character 'c' → Stack is empty, push 'c' → Stack: [c]
Step 6: Next character 'a' → Top of stack is 'c' (different), push 'a' → Stack: [c, a]
Final Result: Convert stack to string → "ca"

Python Code (Optimal Approach):

Python3

. . . .

Java Code (Optimal Approach):

Java

. . . .

Step-by-Step Walkthrough and Visual Examples

Example Walkthrough for Optimal Approach with `s = "abbaca"`

Initialize:
Stack = []
Process 'a':
- Stack is empty → push 'a'
- Stack = [a]
Process 'b':
- Top is 'a', not equal to 'b' → push 'b'
- Stack = [a, b]
Process 'b':
- Top is 'b', equal to 'b' → pop the top
- Stack = [a]
Process 'a':
- Top is 'a', equal to 'a' → pop the top
- Stack = []
Process 'c':
- Stack is empty → push 'c'
- Stack = [c]
Process 'a':
- Top is 'c', not equal to 'a' → push 'a'
- Stack = [c, a]
Final Result:
Join the stack → "ca"

Common Mistakes

Not Handling the Empty String: Always check if the string is empty to avoid errors.
Incorrect Stack Operations: Forgetting to pop when encountering a duplicate or incorrectly comparing characters.
Overcomplicating the Brute Force Approach: Implementing unnecessary loops or redundant checks which may lead to inefficient solutions.
Ignoring Edge Cases: Such as when all characters in the string are the same.

Edge Cases

Empty String: Input: "" → Output: ""
No Duplicates: Input: "abc" → Output: "abc"
All Duplicates: Input: "aa" → Output: ""
Alternating Duplicates: Input: "abab" → Output: "abab"

Variations:

Remove All Adjacent Duplicates in String II: Remove duplicates when a group of k adjacent duplicates appear.
Removing Duplicate Substrings: More complex variations where removal might be based on patterns rather than adjacent duplicates.

1047. Remove All Adjacent Duplicates In String - Detailed Explanation

Problem Statement

Hints Before You Start

Approaches

Brute Force Approach

Idea:

Steps:

Complexity Analysis:

Visual Example:

Python Code (Brute Force):

Java Code (Brute Force):

Optimal Approach (Using a Stack)

Idea:

Steps:

Complexity Analysis:

Visual Example:

Python Code (Optimal Approach):

Java Code (Optimal Approach):

Step-by-Step Walkthrough and Visual Examples

Example Walkthrough for Optimal Approach with s = "abbaca"

Common Mistakes

Edge Cases

Alternative Variations and Related Problems

Variations:

Related Problems for Further Practice:

Example Walkthrough for Optimal Approach with `s = "abbaca"`