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

https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/

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 变量：

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：

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

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

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

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

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

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

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;
        
    }
}

综上，三道括号相关的问题就解决了，其实我们前文 合法括号生成算法 也是括号相关的问题，但是使用的回溯算法技巧，和本文的几道题差别还是蛮大的，有兴趣的读者可以去看看。