• import java.util.Stack;

/**

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.

*/

class Solution {
int ans = 0, bal = 0;
for (int i = 0; i < S.length(); ++i) {
bal += S.charAt(i) == '(' ? 1 : -1;
// It is guaranteed bal >= -1
if (bal == -1) {
ans++;
bal++;
}
}

return ans + bal;
}
}

class Solution2 {

// I'm thinking using stack

Stack<Character> sk = new Stack<>();

int count = 0;

for (char each: S.toCharArray()) {
if (each == '(') {
sk.push(each);
} else if (each == ')') {

if (sk.isEmpty()) {
// key is this case
sk.push(each);
}
else if (sk.peek() == '(') {
sk.pop();
} else {
count += 1;
}
}
}

return count + sk.size();
}
}
}

############

class Solution {
int ans = 0, cnt = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
++cnt;
} else if (cnt > 0) {
--cnt;
} else {
++ans;
}
}
ans += cnt;
return ans;
}
}

• // OJ: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int left = 0, invalidRight = 0;
for (char c : s) {
if (c == '(') ++left;
else if (left) --left;
else ++invalidRight;
}
return invalidRight + left;
}
};

• class Solution:
def minAddToMakeValid(self, s: str) -> int:
ans = cnt = 0
for c in s:
if c == '(':
cnt += 1
elif cnt:
cnt -= 1
else:
ans += 1
ans += cnt
return ans

############

class Solution(object):
"""
:type S: str
:rtype: int
"""
if not S: return 0
stack = []
res = 0
for i, s in enumerate(S):
if '(' == s:
if stack and (stack[-1] == ')'):
cnt = 0
while stack:
if stack.pop() == ')':
cnt -= 1
else:
cnt += 1
if cnt == 0:
break
res += abs(cnt)
stack.append('(')
else:
stack.append(')')
cnt = 0
while stack:
if stack.pop() == ')':
cnt -= 1
else:
cnt += 1
res += abs(cnt)
return res

• func minAddToMakeValid(s string) int {
ans, cnt := 0, 0
for _, c := range s {
if c == '(' {
cnt++
} else if cnt > 0 {
cnt--
} else {
ans++
}
}
ans += cnt
return ans
}

• class Solution {
int curCount = 0;
int length = S.length();
for (int i = 0; i < length; i++) {
char c = S.charAt(i);
if (c == '(')
curCount++;
else {
if (curCount > 0)
curCount--;
else
}
}
}
}

############

class Solution {
int ans = 0, cnt = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
++cnt;
} else if (cnt > 0) {
--cnt;
} else {
++ans;
}
}
ans += cnt;
return ans;
}
}

• // OJ: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int left = 0, invalidRight = 0;
for (char c : s) {
if (c == '(') ++left;
else if (left) --left;
else ++invalidRight;
}
return invalidRight + left;
}
};

• class Solution:
def minAddToMakeValid(self, s: str) -> int:
ans = cnt = 0
for c in s:
if c == '(':
cnt += 1
elif cnt:
cnt -= 1
else:
ans += 1
ans += cnt
return ans

############

class Solution(object):
"""
:type S: str
:rtype: int
"""
if not S: return 0
stack = []
res = 0
for i, s in enumerate(S):
if '(' == s:
if stack and (stack[-1] == ')'):
cnt = 0
while stack:
if stack.pop() == ')':
cnt -= 1
else:
cnt += 1
if cnt == 0:
break
res += abs(cnt)
stack.append('(')
else:
stack.append(')')
cnt = 0
while stack:
if stack.pop() == ')':
cnt -= 1
else:
cnt += 1
res += abs(cnt)
return res

• func minAddToMakeValid(s string) int {
ans, cnt := 0, 0
for _, c := range s {
if c == '(' {
cnt++
} else if cnt > 0 {
cnt--
} else {
ans++
}
}
ans += cnt
return ans
}