921. Minimum Add to Make Parentheses Valid (M)

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

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 是一个合法的括号串。

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

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 配对，会出现什么问题呢？