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

# 921. Minimum Add to Make Parentheses Valid

## Question 921

<https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/>

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
```

### Answer  <a href="#answer" id="answer"></a>

{% tabs %}
{% tab title="v1" %}

```python
class Solution(object):
    def minAddToMakeValid(self, S):

        Sstack = []
        Wrong = []
        for s in S:
            if s == "(":
                Sstack.append(s)
            elif s == ")":
                if len(Sstack) < 1:
                    Wrong.append(s)
                else:
                    Sstack.pop()
        
        return len(Sstack) + len(Wrong)
```

{% endtab %}

{% tab title="v2" %}

```python
class Solution(object):
    def minAddToMakeValid(self, S):

        Sstack = 0
        Wrong = 0
        for s in S:
            if s == "(":
                Sstack += 1
            elif s == ")":
                if Sstack < 1:
                    Wrong += 1
                else:
                    Sstack -= 1
        
        return Sstack + Wrong
                    
        
        
```

{% endtab %}
{% endtabs %}

```
```