Delete the Fewest Parentheses to Balance a String of Only Open and Close Brackets

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

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

Input:  s = "()())"
Output: "()()"

The last ')' has no unpaired '(' before it, so it is deleted.

Example 2

Input:  s = "(()()"
Output: "()()"

The '(' at index 0 is never paired. "(())" also needs only one deletion, but the matching rule removes index 0.

Example 3

Input:  s = "))(("
Output: ""

Delete Unmatched Parentheses Under Left-to-Right Matching

Hints

1. 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?
2. A ')' that arrives when every earlier '(' is already paired can never be paired later.
3. Decide deletions by position: record which indices end up unpaired, then rebuild the string from the remaining characters in their original order.

Approach

Scan s from left to right while keeping a stack of the indices of '(' characters that are still unpaired. On '(' push its index. On ')' with a non-empty stack, pop: the popped index is the closest earlier '(' that is still unpaired, which is exactly the pairing the rule prescribes, so both characters are kept. On ')' with an empty stack there is no unpaired '(' before it, so it stays unpaired and is marked for deletion. When the scan ends, every index still on the stack is a '(' that was never paired and is marked for deletion. The answer is the unmarked characters in their original order.

Invariant: after processing s[0..i], the stack holds, in increasing order, exactly the indices of '(' in that prefix that the standard matching has not yet paired, and its top is the closest one to i. So popping implements 'closest earlier unpaired', and the marked set is exactly the set of characters the rule leaves unpaired. The kept characters form properly nested pairs, so the result is balanced, and, as the statement says, deleting exactly the unpaired characters uses the minimum number of deletions.

Edge cases: the empty string returns the empty string; strings made only of '(' or only of ')' return the empty string; an already balanced string is returned unchanged. When several minimum-deletion results exist, the rule decides which positions go, so deletions are made by position rather than by count. For example, '(()()' becomes '()()' (index 0 is deleted), not '(())'.

• Time complexity: O(n)
• Space complexity: O(n)