LC1541平衡括号字符串的最少插入次数

题目描述

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

任何左括号 '(' 必须对应两个连续的右括号 '))' 。 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。 比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

示例

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。
我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

分析

• 当前步如果是左括号，则左边的问题结束(因为没有连续右括号了)，默认左边问题已经解决，只需要记住当前步多了一个左括号（可以放到栈里也可以计数）。

• 当前步如果是右括号，

  • 如果下一步也是右括号，两个并成一个 "))"，如果Left里有左括号就pop出来一个，和现在的 "))"消去；如果目前没有多余的左括号，就把 "))" 存到 Right2 栈里 (计数也行)
  • 如果下一步是个左括号，那这一步的 ')' 就需要单独处理：
    • 当前Left栈里有左括号，直接在这一步插入一个 ')' 消去一组 "())", 这种借来的 ')'先计入rightDemand中
    • 2.2 当前Left栈空，就在这个')'左右加 '(' 和 ')'，leftDemand 和 rightDemand 各计一个

• 最后多余的每一个 '(' 需要给rightDemand加两个 ')', 每一个"))" 需要给leftDemand加一个'('

代码

import java.util.Stack;

public class LC1541 {
    public static int minInsertions(String s) {
        int i = 0;
        Stack<String> Left = new Stack<>();
        Stack<String> Right2 = new Stack<>();
        int rightDemand = 0;
        int leftDemand = 0;

        while (i < s.length()) {
            if (s.charAt(i) == '(') {
                Left.push("(");
            } else {
                if (i + 1 < s.length() && s.charAt(i + 1) == ')') { // try to combine "))"
                    i += 1; // skip 1
                    if (!Left.empty()) {
                        Left.pop();
                    } else {
                        Right2.push("))");
                    }
                } else {
                    if (!Left.empty()) {
                        // Add ")" to the right immediately and eliminate one left.
                        Left.pop();
                        rightDemand++;
                    } else {
                        // only one single ')', immediately eliminate it
                        leftDemand += 1;
                        rightDemand += 1;
                    }
                }
            }
            i++;
        }

        rightDemand += 2 * Left.size();
        leftDemand += Right2.size();
        return rightDemand + leftDemand;
    }

    public static void main(String[] args) {
        // String str = "))())(";
        String str = "(()))";
        System.out.println(minInsertions(str));
    }
}