LeetCode 1541. Minimum Insertions to Balance a Parentheses String

Question

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 openning parenthesis and '))' as 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

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.

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

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

Input: s = "(((((("
Output: 12
Explanation: Add 12 ')' to balance the string.

Input: s = ")))))))"
Output: 5
Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".

Solution

这个题目可以作为 921. Minimum Add to Make Parentheses Valid的follow up，并且要求只有两个))才能消去一个(，我们利用同样的思路，利用count来记录左括号的数目以及利用res来存当前需要插入的字符总数。遍历整个字符串，如果遇到(我们只需要count++；如果遇到)，则需要考虑后面两个是否为)，如果是的话，我们可以消除一个(或者添加1到res（表示当前没有左括号，需要添加一个），另外，如果第二个字符是( 则我们只需要考虑当前的)，先需要res + 1表示缺失的右括号，另外也需要看左括号是否有，没有的话也需要加上，有的话，就消去。最后就只需要res + 2 * count，这里的两倍count，表示可能有多余的( 需要消除。当然，需要注意如果移动index，如果是连续的两个右括号，则需要index += 2，否则只需要index += 1。

Code

package com.leetcode.stackPriorityQueue.Parentheses;

public class _1541_Minimum_Insertions_to_Balance_a_Parentheses_String {
    // 遇到左括号count++
    // 然后去找连续的两个右括号是否存在
    public int minInsertions(String s) {
        int n = s.length();
        int count = 0;
        int res = 0;
        int index = 0;
        while (index < n) {
            if (s.charAt(index) == '(') {
                count++;
                index++;
            } else if (s.charAt(index) == ')') {
                if (index + 1 < n && s.charAt(index + 1) == ')') {
                    if (count > 0) count--;
                    else res += 1;
                    index += 2;
                } else { // 走完或者是第二个char不是')'
                    if (count > 0) count--; // 这个还是要消除前面的'('
                    else res++; // 不然就是需要加上
                    res += 1; // 这个表示少的那个')'
                    index += 1; // 继续走一步。
                }
            }
        }
        return res + 2 * count;
    }
}

Reference

• 921. Minimum Add to Make Parentheses Valid