1. Remove All Adjacent Duplicates In String (LeetCode)
Model answer
The task
Given a string, repeatedly remove any pair of equal characters that are next to each other. Return the string left after no such pair remains.
Key idea
Process the characters from left to right using a stack. The stack represents the reduced string so far: if the next character matches its top, remove the top; otherwise, add the character.
Approach
- Start with an empty stack.
- Visit each character in the input string.
- If it matches the stack’s top, pop the top.
- Otherwise, push the character.
- Join the stack to produce the result.
Each decision leaves the processed prefix fully reduced. Removing a pair can expose a new adjacent pair, but the stack handles that naturally when later characters are processed.
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for char in s:
if stack and stack[-1] == char:
stack.pop()
else:
stack.append(char)
return "".join(stack)
Complexity:
- Time: O(n), since each character is pushed at most once and popped at most once.
- Space: O(n), for the stack in the worst case.
Common follow-ups
- What if each character must be removed when it appears in a run of at least
kequal characters? Store character counts on the stack and pop a group when its count reachesk. - Can this be done in place on a mutable character array? Use a write index as a stack pointer, overwriting the processed prefix.
- What if removals follow a specified priority or multiple different patterns? Clarify the rules first; a stack may still work, but the match and removal logic may need to change.