Minimum Add to Make Parentheses Valid

You may insert either ( or ) anywhere in the parentheses string s. Return the fewest insertions needed to make the parentheses balanced: every closing parenthesis must match an earlier unmatched opening parenthesis, and no opening parenthesis may remain unmatched.

Example 1:

Input: s = "("

Output: 1

Explanation: Append one closing parenthesis to obtain "()".

Example 2:

Input: s = ")"

Output: 1

Explanation: Insert one opening parenthesis before the existing character to obtain "()".

Example 3:

Input: s = "()"

Output: 0

Explanation: The opening parenthesis already has a matching closing parenthesis, so no insertion is needed.

Constraints:

• 1 <= s.length <= 1000
• Each character is ( or ).