Minimum Insertions to Balance a Parentheses String
Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
- Any left parenthesis
'('must have a corresponding two consecutive right parentheses'))'. - A left parenthesis
'('must come before its corresponding two consecutive right parentheses'))'.
In other words, treat '(' as an opening parenthesis and '))' as a closing parenthesis.
You can insert the characters '(' and ')' at any position of the string to balance it if needed.
Return the minimum number of insertions needed to make s balanced.
Example 1
Input
s = "(()))"Output
1The second '(' has two matching '))', but the first '(' has only ')' matching, so one more ')' must be added at the end.
Example 2
Input
s = "())"Output
0The string is already balanced.
Constraints
- 1 <= s.length <= 10^5
- s consists of '(' and ')' only.