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.The key idea in #1047 Remove All Adjacent Duplicates In String is to repeatedly eliminate pairs of identical neighboring characters until no such pair remains. A clean way to simulate this behavior is by using a stack-like approach. As you iterate through the string, compare the current character with the most recent character stored in the stack.
If the top element of the stack matches the current character, it means an adjacent duplicate is found, so you remove the top element. Otherwise, push the current character onto the stack. This mimics the process of continuously removing adjacent duplicates as they appear.
After processing all characters, the stack will contain the final sequence without adjacent duplicates. The result can be constructed by joining the characters in the stack. This approach is efficient because each character is pushed and popped at most once, resulting in O(n) time complexity and O(n) auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-Based Simulation | O(n) | O(n) |
| String Builder as Stack | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use a stack to process everything greedily.
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4char* removeDuplicates(char* s) {
5 int len = strlen(
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.
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.
Time Complexity: O(n), with n being the string length.
Space Complexity: O(1), since it modifies the original string in place.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem are common in technical interviews at major tech companies. Interviewers use it to test understanding of stacks, string processing, and efficient linear-time solutions.
A stack is the most suitable data structure for this problem because it naturally supports checking and removing the most recent character. In practice, many implementations use a stack or a dynamic string structure like a StringBuilder acting as a stack.
The optimal approach uses a stack to track characters while iterating through the string. If the current character matches the stack's top element, it is removed; otherwise it is added. This ensures each character is processed at most twice, giving O(n) time complexity.
Yes, the problem can be solved using a mutable string structure such as a StringBuilder or array acting like a stack. The logic remains the same: compare the last stored character with the current one and remove or append accordingly.
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.