Balance Parentheses

Problem Given a string of parentheses, return the minimum number of operations (insertions and/or removals) needed to make it valid — or, in the simpler variant, just determine whether it is balanced.

Input / Output

• Input: string s of '(' and ')'.
• Output: minimum operations to make s valid (0 means already balanced).

Constraints

• |s| up to 10^5; O(n) time, O(1) space expected.

Example

• s = "()))((" → 4 (two unmatched ')' and two unmatched '(').
• s = "(()" → 1.