Remove All Adjacent Duplicates In String - Solution & Explanation
Problem Statement
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Example 1:
Input: s = "abbaca" Output: "ca" Explanation: For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
Example 2:
Input: s = "azxxzy" Output: "ay"
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.
Approach Overview
Problem Overview: Given a string s, repeatedly remove pairs of adjacent duplicate characters until no such pairs remain. The final string must contain no two neighboring characters that are equal. The challenge is handling cascading removals where deleting one pair exposes another.
Approach 1: Stack-Based Approach (O(n) time, O(n) space)
This problem maps naturally to a stack. Iterate through the string character by character. For each character, compare it with the top of the stack. If they match, pop the stack because the pair cancels out. If they differ, push the current character onto the stack. This simulates the repeated removal process without actually modifying the string multiple times.
The key insight: the stack always stores the current valid result with no adjacent duplicates. When a duplicate appears, the top element represents the previous character, so you can remove the pair instantly. Each character is pushed and popped at most once, giving O(n) time complexity and O(n) space for the stack. This approach is straightforward and widely used in interview solutions involving adjacent cancellation problems.
Approach 2: Two-Pointer Approach (O(n) time, O(1) extra space)
You can simulate the stack using two pointers on a character array. Convert the string into an array and maintain a write pointer that represents the end of the current valid result. Iterate through the array with a read pointer. For each character, write it to the position indicated by the write pointer.
After writing, check whether the last two characters in the result are equal. If they match, move the write pointer back by two positions, effectively removing the pair. Otherwise, advance the pointer normally. This technique uses the input array itself as the stack buffer.
This method still processes each character once, so the time complexity remains O(n). Since it modifies the array in place, the extra memory overhead is O(1). It's a great example of using pointer manipulation in string processing and often preferred when minimizing memory allocations.
Recommended for interviews: The stack-based solution is the most commonly expected answer because it directly models the removal behavior and clearly demonstrates understanding of stack operations like push and pop. The two-pointer variant shows deeper optimization skills by eliminating extra memory. Starting with the stack approach and then mentioning the in-place optimization is a strong interview strategy.
Approach 1: Stack-Based Approach
Use a stack data structure to efficiently remove adjacent duplicates. Traverse through the string, and for each character, check the top of the stack. If the top of the stack is equal to the current character, pop the stack. Otherwise, push the current character onto the stack. Finally, reconstruct the string from the stack.
The solution iteratively checks each character of the string. If the character matches the top of the stack, it removes it (indicating an adjacent duplicate removal). Otherwise, it pushes the character onto the stack. This simulates the removal of adjacent duplicates effectively.
Complexity
Time Complexity: O(n), where n is the length of the string since we traverse the string once.
Space Complexity: O(n), as in the worst case, the stack may need to store all characters.
Approach 2: Two-Pointer Approach
This approach also simulates stack behavior but uses a two-pointer technique on the same string to efficiently manage space without using additional data structures. It leverages the properties of strings and index manipulation to override adjacent duplicates.
The two-pointer method directly modifies the input string array by using `i` as the effective end of the currently processed string. Whenever a duplicate is detected, we backtrack the `i` pointer, simulating a pop operation. This way, space usage is minimized as no extra stack structure is created.
Complexity
Time Complexity: O(n), with n being the string length.
Space Complexity: O(1), since it modifies the original string in place.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n), where n is the length of the string since we traverse the string once. |
| Two-Pointer Approach | Time Complexity: O(n), with n being the string length. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Approach | O(n) | O(n) | Best general solution. Clear logic and commonly expected in interviews. |
| Two-Pointer (In-place Stack Simulation) | O(n) | O(1) | When minimizing extra memory. Uses the input array as a stack buffer. |
Video Solution
LeetCode Remove All Adjacent Duplicates In String Solution Explained - Java • Nick White • 30,029 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove All Adjacent Duplicates In String easy or hard?
Remove All Adjacent Duplicates In String Python/Java solution
How to solve Remove All Adjacent Duplicates In String in O(n)?
What is the best approach for Remove All Adjacent Duplicates In String?
Is Remove All Adjacent Duplicates In String asked at Google/Amazon/Meta?
What data structure is used in Remove All Adjacent Duplicates In String?
What is the time complexity of Remove All Adjacent Duplicates In String?
Ready to solve this problem?
Practice Remove All Adjacent Duplicates In String with our built-in code editor and test cases.
Practice on FleetCode