Repeatedly Delete Adjacent Duplicate Pairs or Whole Runs of Equal Characters
Company: Whatnot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a string `s` of lowercase letters and a flag `remove_whole_runs`. Delete adjacent duplicates repeatedly until none remain, and return the final string.
The interview first asked for the base rule, which deletes equal adjacent characters two at a time. The follow-up dropped the fixed group size: whenever equal characters are adjacent, all of them are deleted, however many there are. Here one function covers both rules, selected by the flag.
### Function Signature
```python
def remove_adjacent_duplicates(s: str, remove_whole_runs: bool) -> str:
```
### Rules
- A *run* is a maximal block of consecutive equal characters. For example, `"abbbac"` has the runs `a`, `bbb`, `a`, `c`.
- When `remove_whole_runs` is `False`: repeatedly choose two adjacent equal characters and delete both. Stop when no two adjacent characters are equal. The final string is the same whichever pair is chosen at each step.
- When `remove_whole_runs` is `True`: repeatedly delete the entire leftmost run of length two or more. Stop when every run has length one. Here the order of deletions can change the result, so the leftmost rule is part of the specification.
- After a deletion, the characters on either side of the deleted block become adjacent and may form a new run. Characters that are never deleted keep their original order.
- Return the final string, which may be empty.
### Constraints
- `1 <= len(s) <= 10^5`
- `s` consists only of lowercase English letters `a` to `z`.
- `remove_whole_runs` is `True` or `False`.
### Examples
**Example 1**
```text
Input: s = "abbaca", remove_whole_runs = False
Output: "ca"
```
Deleting `bb` gives `"aaca"`, and deleting `aa` gives `"ca"`.
**Example 2**
```text
Input: s = "abbbac", remove_whole_runs = True
Output: "c"
```
The run `bbb` is deleted, giving `"aac"`; then the run `aa` is deleted, giving `"c"`. With `remove_whole_runs = False`, the same string gives `"abac"`: one pair of `b` characters is deleted and a single `b` remains.
**Example 3**
```text
Input: s = "abbaa", remove_whole_runs = True
Output: ""
```
The leftmost run `bb` goes first, leaving `"aaa"`, which is then deleted. Deleting the final `aa` first would have left `"abb"` and then `"a"`, which the leftmost rule does not allow.
Overview: A string coding problem with two modes: repeatedly delete pairs of equal adjacent characters, or, as the follow-up, delete whole runs of equal adjacent characters, always the leftmost run first, and return what remains. It tests simulating cascading deletions efficiently and handling runs that merge after a deletion.
You are given a string `s` of lowercase English letters and a boolean flag `remove_whole_runs`. Delete adjacent duplicates repeatedly until none remain, and return the final string.
The interview first asked for a base rule that deletes equal adjacent characters two at a time. The follow-up dropped the fixed group size: whenever equal characters are adjacent, all of them are deleted, however many there are. Here one function covers both rules, selected by the flag.
### Rules
- A *run* is a maximal block of consecutive equal characters. For example, `"abbbac"` has the runs `a`, `bbb`, `a`, `c`.
- When `remove_whole_runs` is `False`: repeatedly choose two adjacent equal characters and delete both. Stop when no two adjacent characters are equal. The final string is the same whichever pair is chosen at each step.
- When `remove_whole_runs` is `True`: repeatedly delete the entire **leftmost** run of length two or more. Stop when every run has length one. Here the order of deletions can change the result, so the leftmost rule is part of the specification.
- After a deletion, the characters on either side of the deleted block become adjacent and may form a new run. Characters that are never deleted keep their original order.
- Return the final string, which may be empty.
Implement `remove_adjacent_duplicates(s, remove_whole_runs)`.
### Example 1
```text
Input: s = "abbaca", remove_whole_runs = False
Output: "ca"
```
Deleting `bb` gives `"aaca"`, and deleting `aa` gives `"ca"`.
### Example 2
```text
Input: s = "abbaa", remove_whole_runs = True
Output: ""
```
The leftmost run `bb` goes first, leaving `"aaa"`, which is then deleted. Deleting the final `aa` first would have left `"abb"` and then `"a"`, which the leftmost rule does not allow. For comparison, `s = "abbbac"` gives `"c"` with `remove_whole_runs = True` (delete `bbb`, then the new run `aa`) and `"abac"` with `False` (one pair of `b` characters is deleted and a single `b` remains).
### Constraints
- `1 <= len(s) <= 10^5`
- `s` consists only of lowercase English letters `a` to `z`.
- `remove_whole_runs` is `True` or `False`.
No numeric value is computed or returned, so nothing approaches 2^31 - 1; the returned string has length between 0 and `len(s)`.
Constraints
- 1 <= len(s) <= 10^5
- s consists only of lowercase English letters a to z.
- remove_whole_runs is True or False.
Examples
Input: ('abbaca', False)
Expected Output: 'ca'
Explanation: Source example 1: deleting 'bb' makes the two a's adjacent, that pair is deleted too, leaving 'ca'.
Input: ('abbaa', True)
Expected Output: ''
Explanation: Source example 3, leftmost rule: 'bb' goes first, then the merged run 'aaa'; deleting both runs at once or the right run first would leave 'a'.
Hints
- After any deletion, only the two characters that border the removed block become newly adjacent. Which part of the string can still change, and which part is already final?
- In whole-run mode, everything to the left of the leftmost run of length two or more has no two equal neighbours. Where, relative to what you have already read, can the next deletion happen?
- Work through "abbaa" in both modes by hand and compare with the examples; the whole-run result depends on deleting the leftmost run first.