Minimum Add to Make Parentheses Valid

Problem: Minimum Add to Make Parentheses Valid Given a string s consisting only of '(' and ')'. In one operation, you may add one parenthesis character '(' or ')' at any position of the string. Return the minimum number of additions required to make s a valid parentheses string. A valid parentheses string is defined as follows: The empty string is valid. If A is valid, then (A) is valid. If A and B are valid, then AB is valid. Requirement Solve it using O(1) extra space. Input Format One line containing the string s, consisting only of '(' and ')'. Output Format Print one integer: the minimum number of parentheses to add. Constraints 1 <= len(s) <= 10^5 s[i] is either '(' or ')' Example Input: ()) Output: 1 Explanation: Add one '(' to make ()() or (()). Example Input ()) Output 1