> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/1541.-minimum-insertions-to-balance-a-parentheses-string-m.md).

# 1541. Minimum Insertions to Balance a Parentheses String (M)

Given a parentheses string `s` containing only the characters `'('` and `')'`. A parentheses string is **balanced** if:

* Any left parenthesis `'('` must have a corresponding two consecutive right parenthesis `'))'`.
* Left parenthesis `'('` must go before the corresponding two consecutive right parenthesis `'))'`.

In other words, we treat `'('` as an opening parenthesis and `'))'` as a closing parenthesis.

* For example, `"())"`, `"())(())))"` and `"(())())))"` are balanced, `")()"`, `"()))"` and `"(()))"` are not balanced.

You can insert the characters `'('` and `')'` at any position of the string to balance it if needed.

Return *the minimum number of insertions* needed to make `s` balanced.

 

**Example 1:**

```
Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.
```

**Example 2:**

```
Input: s = "())"
Output: 0
Explanation: The string is already balanced.
```

**Example 3:**

```
Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.
```

 

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of `'('` and `')'` only.

### Solution:

现在假设 1 个左括号需要匹配 2 个右括号才叫做合法的括号组合，那么给你输入一个括号串 `s`，请问你如何计算使得 `s` 合法的最小插入次数呢？

**核心思路还是和刚才一样，通过一个 `need` 变量记录对右括号的需求数，根据 `need` 的变化来判断是否需要插入**。

第一步，我们按照刚才的思路正确维护 `need` 变量：

```cpp
int minInsertions(string s) {
    // need 记录需右括号的需求量
    int res = 0, need = 0;
    
    for (int i = 0; i < s.size(); i++) {
        // 一个左括号对应两个右括号
        if (s[i] == '(') {
            need += 2;
        }
        
        if (s[i] == ')') {
            need--;
        }
    }
    
    return res + need;
}
```

现在想一想，当 `need` 为什么值的时候，我们可以确定需要进行插入？

**首先，类似第一题，当 `need == -1` 时，意味着我们遇到一个多余的右括号，显然需要插入一个左括号**。

比如说当 `s = ")"`，我们肯定需要插入一个左括号让 `s = "()"`，但是由于一个左括号需要两个右括号，所以对右括号的需求量变为 1：

```cpp
if (s[i] == ')') {
    need--;
    // 说明右括号太多了
    if (need == -1) {
        // 需要插入一个左括号
        res++;
        // 同时，对右括号的需求变为 1
        need = 1;
    }
}
```

**另外，当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号**。因为一个左括号需要两个右括号嘛，右括号的需求必须是偶数，这一点也是本题的难点。

**res表示的是当前遍历过程中为了配平当前的状态，所需要插入左括号或是右括号的总次数，need表示的是遍历结束后仍需要的右括号数量**

所以遇到左括号时要做如下判断：

```cpp
if (s[i] == '(') {
    need += 2;
    if (need % 2 == 1) {
        // 插入一个右括号
        res++;
        // 对右括号的需求减一
        need--;
    }
}
```

综上，我们可以写出正确的代码：

```cpp
int minInsertions(string s) {
    int res = 0, need = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            need += 2;
            if (need % 2 == 1) {
                res++;
                need--;
            }
        }
        
        if (s[i] == ')') {
            need--;
            if (need == -1) {
                res++;
                need = 1;
            }
        }
    }
    
    return res + need;
}

AnotherVersion:
class Solution {
    public int minInsertions(String s) {
        
        
        
        int resLeft = 0;
        int resRight = 0;
        int need = 0;
        for(int i = 0; i< s.length() ;i++)
        {
            if(s.charAt(i) == '(')
            {
                need += 2; 
                if(need%2 == 1)
                {
                    resRight++;
                    need--;
                }
            }
            if(s.charAt(i) == ')')
            {
                need--;
                if(need == -1)
                {
                    need = 1;
                    resLeft++;
                }
            }
        }
        return resLeft+resRight+need;
        
    }
}
```

综上，三道括号相关的问题就解决了，其实我们前文 [合法括号生成算法](https://labuladong.gitee.io/algo/4/29/114/) 也是括号相关的问题，但是使用的回溯算法技巧，和本文的几道题差别还是蛮大的，有兴趣的读者可以去看看。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/8.data-structure/1541.-minimum-insertions-to-balance-a-parentheses-string-m.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.