# 921. Minimum Add to Make Parentheses Valid

## Description

A parentheses string is valid if and only if:

• It is the empty string,
• 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.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

• For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

Example 1:

Input: s = "())"
Output: 1


Example 2:

Input: s = "((("
Output: 3


Constraints:

• 1 <= s.length <= 1000
• s[i] is either '(' or ')'.

## Solutions

• 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;
}
}

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

• 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


• 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
}

• function minAddToMakeValid(s: string): number {
const stk: string[] = [];
for (const c of s) {
if (c === ')' && stk.length > 0 && stk.at(-1)! === '(') {
stk.pop();
} else {
stk.push(c);
}
}
return stk.length;
}