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.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), with n being the string length.
Space Complexity: O(1), since it modifies the original string in place.
| 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. |
Remove All Adjacent Duplicates in String II - Leetcode 1209 - Python • NeetCode • 53,400 views views
Watch 9 more video solutions →Practice Remove All Adjacent Duplicates In String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor