# Minimum Add To Make Parentheses Valid Problem

## Description

LeetCode Problem 921.

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:

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

Example 2:

``````1
2
Input: s = "((("
Output: 3
``````

Example 3:

``````1
2
Input: s = "()"
Output: 0
``````

Example 4:

``````1
2
Input: s = "()))(("
Output: 4
``````

Constraints:

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

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int res = 0, n = S.size(), balance = 0;
for (int i = 0; i < n; i++) {
balance += S[i] == '(' ? 1 : -1;
if (balance == -1) {
res++;
balance++;
}
}
return res + balance;
}
};
``````