Delete the Fewest Parentheses to Balance a String of Only Open and Close Brackets
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a string `s` that contains only the characters `'('` and `')'`. Delete the minimum number of characters so that the remaining string is balanced, and return the remaining string.
A string is balanced when every `'('` can be paired with a later `')'` and every `')'` with an earlier `'('`, with pairs properly nested. The empty string is balanced.
### Function Signature
```python
def balance_parentheses(s: str) -> str:
```
### Rules
- Only deletions are allowed. The remaining characters keep their original order.
- Several different strings can sometimes be reached with the same minimum number of deletions. The answer is defined by the standard matching. Scan from left to right, and pair each `')'` with the closest earlier `'('` that is still unpaired. A `')'` with no unpaired `'('` before it stays unpaired, and so does every `'('` still unpaired at the end. Delete exactly the unpaired characters. This deletes the minimum possible number.
- Return the remaining string, which may be empty.
### Constraints
- `0 <= len(s) <= 10^5`
- Every character of `s` is `'('` or `')'`.
### Examples
**Example 1**
```text
Input: s = "()())"
Output: "()()"
```
The last `')'` has no unpaired `'('` before it, so it is deleted.
**Example 2**
```text
Input: s = "(()()"
Output: "()()"
```
The `'('` at index `0` is never paired. `"(())"` also needs only one deletion, but the matching rule removes index `0`.
**Example 3**
```text
Input: s = "))(("
Output: ""
```
Overview: Given a string of only open and close parentheses, delete the fewest characters so the rest is balanced and return the resulting string, using standard left-to-right matching to define a unique answer. Tests bracket matching, linear-time scanning and careful handling of leftover unmatched characters.