Remove All Adjacent Duplicates In String
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: In "abbaca" we remove "bb" to get "aaca", then remove "aa" to get "ca". No more adjacent duplicates.
Example 2:
Input: s = "azxxzy"
Output: "ay"
Explanation: In "azxxzy" we remove "xx" to get "azzy", then remove "zz" to get "ay". No more adjacent duplicates.
Example 3:
Input: s = "abcdef"
Output: "abcdef"
Explanation: No adjacent duplicates exist, so the string remains unchanged.
Constraints
1 <= s.length <= 10^5s consists of lowercase English letters
Complexity
Show Complexity
- Time:
O(n) - Space:
O(n)
Hints
Show Hints
- Pattern
- Stack-based character processing
- Approach
- Use a stack: if current char equals stack top, pop (remove pair); otherwise push. Final stack is the answer.
- Complexity
- Process each character once, stack operations are O(1)
Solutions
Show PY Solution
def solution(s: str) -> str:
stack = []
for c in s:
if stack and stack[-1] == c:
stack.pop()
else:
stack.append(c)
return "".join(stack)