Problem Brief

Balancing Parentheses

FULLTIMEOA

Given a string that consists of left and right parentheses, '(' and ')', balance the parentheses by inserting parentheses as necessary. Determine the minimum number of characters that must be inserted.

Function Description

Complete the function balanceParentheses in the editor.

balanceParentheses has the following parameter:

String s: a string of parentheses

Returns

int: the minimum number of insertions needed

♫⋆｡♪ ₊˚♬ ﾟ.Huge Thanks to spike!!𓂃 🐳𓈒𓏸

1Example 1

Input

s = "()))"

Output

Explanation

Insert a '(' 2 times at the beginning of the string to make it valid: '((()))'

2Example 2

Input

s = "))(("

Output

Explanation

Insert 2 left parentheses at the start and 2 right parentheses at the end of the string to get "(()))(())" after 4 insertions.

3Example 3

Input

s = "(()))"

Output

Explanation

Insert 1 left paranthesis at the left end of the string to get '((()))'. The string is balanced after 1 insertion.

4Example 4

Input

s = "()()"

Output

Explanation

The sequence is already valid.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ length of s ≤ 10⁵