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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Greedy algorithms

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]