Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:

It is the empty string, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
 
Example 1:
Input: "())"
Output: 1


Example 2:
Input: "((("
Output: 3


Example 3:
Input: "()"
Output: 0


Example 4:
Input: "()))(("
Output: 4
 



Note:

S.length <= 1000
S only consists of '(' and ')' characters.

Difficulty: interview

Starter code:

class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        

Solutions:
class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        if not S:
            return 0
        
        stack = []
        
        add = 0
        for c in S:
            if c == '(':
                stack.append(c)
            elif c == ')':
                if stack:
                    stack.pop()
                else:
                    add += 1
        
        add += len(stack)
        
        return add

class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        res,need=0,0
        for i in range(len(S)):
            if S[i]=='(':
                need+=1
            if S[i]==')':
                need-=1
                if need==-1:
                    need=0
                    res+=1
        return res+need


class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        if not S:
            return 0
        N = len(S)
        open_brackets = [0]*N
        close_brackets = [0]*N
        
        ans = 0
        for i, c in enumerate(S):
            if i>0:
                open_brackets[i] = open_brackets[i-1]
                close_brackets[i] = close_brackets[i-1]
            if c == '(':
                open_brackets[i] += 1
            elif c == ')':
                close_brackets[i] += 1
            
            if close_brackets[i] > open_brackets[i]:
                diff = close_brackets[i]-open_brackets[i]
                ans += diff
                open_brackets[i] += diff
                
        return ans+open_brackets[-1]-close_brackets[-1]