> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/minimum-add-to-make-parentheses-valid.md).

# Minimum Add to Make Parentheses Valid

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:**

1. `S.length <= 1000`
2. `S` only consists of `'('` and `')'` characters.

```java
class Solution {
    public int minAddToMakeValid(String S) {
        int not_opened = 0, not_closed = 0;
        for (int i = 0; i < S.length(); ++i) {
            if (S.charAt(i) == '(') {
                not_closed++;
            } else if (not_closed > 0) {
                not_closed--;
            } else {
                not_opened++;
            }
        }
        return not_opened + not_closed;
    }
}
```