Watch 10 video solutions for Remove All Adjacent Duplicates In String, a easy level problem involving String, Stack. This walkthrough by Nick White has 29,923 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105s consists of lowercase English letters.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 | 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. |