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.
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 the pairs properly nested. The empty string is balanced.
Implement `balance_parentheses(s)`, which returns the remaining string.
### 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 `s` 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 `'('` that is still unpaired when the scan ends. Delete exactly the unpaired characters; this deletes the minimum possible number.
- Return the remaining string, which may be empty.
### 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. `"(())"` can also be reached with one deletion, but the matching rule removes index `0`.
### Constraints
- `0 <= len(s) <= 10^5`
- Every character of `s` is `'('` or `')'`.
- No value in this problem exceeds 2^31 - 1: the only sizes involved are string lengths of at most 10^5, so 32-bit integers suffice in every language.
Constraints
- 0 <= len(s) <= 10^5
- Every character of s is '(' or ')'.
Examples
Input: ('()())',)
Expected Output: '()()'
Explanation: Source example 1: the final ')' has no unpaired '(' before it and is deleted; the matching rule gives '()()' rather than the equally short '(())'.
Input: ('(()()',)
Expected Output: '()()'
Explanation: Source example 2: the '(' at index 0 is never paired and is deleted, giving '()()' and not '(())'.
Hints
- Apply the matching rule literally while scanning from left to right: when a ')' arrives, which '(' does it pair with, and what must you remember about the '(' characters seen so far?
- A ')' that arrives when every earlier '(' is already paired can never be paired later.
- Decide deletions by position: record which indices end up unpaired, then rebuild the string from the remaining characters in their original order.