Remove All Adjacent Duplicate Pairs
Company: Whatnot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Remove All Adjacent Duplicate Pairs
Given a string `s`, repeatedly remove pairs of equal adjacent characters. A removal can make a new equal pair adjacent, which must also be removed. Return the final string after no such pair remains.
The final result is uniquely determined by processing the characters from left to right.
### Function Signature
```python
def remove_adjacent_duplicates(s: str) -> str:
```
### Examples
```text
Input: s = "abbaca"
Output: "ca"
Input: s = "azxxzy"
Output: "ay"
```
### Constraints
- `0 <= len(s) <= 200_000`
- `s` contains arbitrary Unicode characters; equality is exact character equality.
- Return the empty string if every character is removed.
### Clarifications
- Remove duplicate characters in pairs, not an entire run in one operation. For example, `"aaa"` becomes `"a"`.
- Continue until the string is stable; a single non-overlapping pass is not sufficient.
### Hints
- Look for a representation in which the most recently retained character can be inspected in constant time.
- The target complexity is linear time with linear worst-case auxiliary space.
Quick Answer: Repeatedly remove equal adjacent character pairs until a Unicode string becomes stable. Use a stack-like single pass to expose newly adjacent duplicates, preserve pairwise run behavior such as three equal characters becoming one, and achieve linear time.
Repeatedly remove adjacent equal-character pairs until none remain. New pairs created by earlier removals must also disappear. Equality is exact Unicode character equality.
Constraints
- The string may contain up to 200,000 Unicode characters.
- Duplicate characters are removed in pairs, not whole runs.
- An empty or fully removed input returns an empty string.
Examples
Input: ('abbaca',)
Expected Output: 'ca'
Explanation: A removal exposes another removable pair.
Input: ('azxxzy',)
Expected Output: 'ay'
Explanation: Nested cancellation is handled.
Hints
- Use the retained prefix as a stack.
- Compare each incoming character with the most recently retained one.