# 921. Minimum Add to Make Parentheses Valid

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 ')'.

## Code Snippet

```
package com.ideserve.sakshi.questions;

/**
* <b>IDeserve <br>
* Minimum Add to Make Parentheses Valid
*
* @author Sakshi
*/
class Solution {
// Consider all kind of strings like '(()', ')))((('
int n = s.length();
int openMinusClose = 0;
int closeMinusOpen = 0;
int i = 0;
while (i < n) {
if (s.charAt(i) == '(') {
openMinusClose++;
} else if (openMinusClose > 0 && s.charAt(i) == ')') {
openMinusClose--;
} else if (s.charAt(i) == ')') {
closeMinusOpen++;
}
i++;
}
return openMinusClose + closeMinusOpen;
}
}
```

## Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)