A string s contains only the characters ( and ). You may insert a ( or ) anywhere in the string. Return the minimum number of insertions needed to make the string balanced (every ( has a matching ) that comes after it, properly nested).
Examples
Input: s = "())"
Output: 1
Input: s = "((("
Output: 3
Input: s = "))(("
Output: 4
Explanation: two closers have nothing before them and two openers are never closed.
Constraints
0 <= len(s) <= 10**5- Target:
O(n)time,O(1)extra space is possible
Goals
- Track unmatched openers while scanning
- Count closers that arrive with nothing to match