# 921. Minimum Add to Make Parentheses Valid (M)

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

### Solution:

给你输入一个字符串 `s`，你可以在其中的任意位置插入左括号 `(` 或者右括号 `)`，请问你最少需要几次插入才能使得 `s` 变成一个合法的括号串？

比如说输入 `s = "())("`，算法应该返回 2，因为我们至少需要插入两次把 `s` 变成 `"(())()"`，这样每个左括号都有一个右括号匹配，`s` 是一个合法的括号串。

这其实和前文的判断括号合法性非常类似，我们直接看代码：

```cpp
int minAddToMakeValid(string s) {
    // res 记录插入次数
    int res = 0;
    // need 变量记录右括号的需求量
    int need = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            // 对右括号的需求 + 1
            need++;
        }
        
        if (s[i] == ')') {
            // 对右括号的需求 - 1
            need--;

            if (need == -1) {
                need = 0;
                // 需插入一个左括号
                res++;
            }
        }
    }
    
    return res + need;
}
```

这段代码就是最终解法，**核心思路是以左括号为基准，通过维护对右括号的需求数 `need`，来计算最小的插入次数**。需要注意两个地方：

**1、当 `need == -1` 的时候意味着什么**？

因为只有遇到右括号 `)` 的时候才会 `need--`，`need == -1` 意味着右括号太多了，所以需要插入左括号。

比如说 `s = "))"` 这种情况，需要插入 2 个左括号，使得 `s` 变成 `"()()"`，才是一个合法括号串。

**2、算法为什么返回 `res + need`**？

因为 `res` 记录的左括号的插入次数，`need` 记录了右括号的需求，当 for 循环结束后，若 `need` 不为 0，那么就意味着右括号还不够，需要插入。

比如说 `s = "))("` 这种情况，插入 2 个左括号之后，还要再插入 1 个右括号，使得 `s` 变成 `"()()()"`，才是一个合法括号串。

以上就是这道题的思路，接下来我们看一道进阶题目，如果左右括号不是 1:1 配对，会出现什么问题呢？