Remove All Adjacent Duplicates In String
Problem Description
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 <= 105
sconsists of lowercase English letters.
Solve it on LeetCode
Approaches
1. Using a Stack
Intuition:
The problem requires removal of adjacent duplicates in the given string s. This can be efficiently solved using a stack. The basic idea is to iterate over each character of the string, and use a stack to keep track of characters, ensuring that whenever two consecutive characters are the same, we pop them from the stack, effectively removing those duplicates.
Algorithm:
- Initialize an empty stack to store characters.
- Iterate through each character
cin the strings. - For each character, check if the stack is not empty and the top of the stack is equal to
c. - If true, pop the top element (this means we've found a duplicate).
- Else, push the current character
conto the stack. - Finally, construct the resulting string from the characters left in the stack.
Code:
- Time Complexity: O(n), where n is the length of the string
s. Each character is pushed and popped from the stack at most once. - Space Complexity: O(n) in the worst case where there are no adjacent duplicates, and the stack contains all characters of the string.