Question

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

English Version

题目描述

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

• 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
• 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

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

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

 

示例 1：

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

示例 2：

输入：s = "())"
输出：0
解释：字符串已经平衡了。

示例 3：

输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。

示例 4：

输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。

示例 5：

输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。

 

提示：

• 1 <= s.length <= 10^5
• s 只包含 '(' 和 ')' 。

解法

方法一：贪心

我们用 $x$ 表示字符串中待匹配的左括号的数量，初始时为 $0$。遍历字符串 $s$：

如果遇到左括号，则 $x$ 的值加 $1$；如果遇到右括号，我们分情况讨论：

• 如果有两个连续的右括号，那么我们先让指针往后移动一位；否则，我们需要插入一个右括号，使得出现两个连续的右括号，因此插入次数加 $1$；
• 如果 $x = 0$，说明当前没有待匹配的左括号，我们需要插入一个左括号，用于匹配上面准备好的两个连续的右括号，因此插入次数加 $1$；否则，我们让 $x$ 的值减 $1$。

然后指针往后移动一位，继续下一次遍历。

遍历结束后，如果 $x = 0$，说明字符串已经平衡，返回插入次数；否则，说明字符串中有待匹配的左括号，我们需要再插入 $2 \times x$ 个右括号，使得字符串变成平衡字符串，返回插入次数。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

class Solution:
  def minInsertions(self, s: str) -> int:
    ans = x = 0
    i, n = 0, len(s)
    while i < n:
      if s[i] == '(':
        # 待匹配的左括号加 1
        x += 1
      else:
        if i < n - 1 and s[i + 1] == ')':
          # 有连续两个右括号，i 往后移动
          i += 1
        else:
          # 只有一个右括号，插入一个
          ans += 1
        if x == 0:
          # 无待匹配的左括号，插入一个
          ans += 1
        else:
          # 待匹配的左括号减 1
          x -= 1
      i += 1
    # 遍历结束，仍有待匹配的左括号，说明右括号不足，插入 x << 1 个
    ans += x << 1
    return ans

class Solution {
  public int minInsertions(String s) {
    int ans = 0, x = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '(') {
        ++x;
      } else {
        if (i < n - 1 && s.charAt(i + 1) == ')') {
          ++i;
        } else {
          ++ans;
        }
        if (x == 0) {
          ++ans;
        } else {
          --x;
        }
      }
    }
    ans += x << 1;
    return ans;
  }
}

class Solution {
public:
  int minInsertions(string s) {
    int ans = 0, x = 0;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      if (s[i] == '(') {
        ++x;
      } else {
        if (i < n - 1 && s[i + 1] == ')') {
          ++i;
        } else {
          ++ans;
        }
        if (x == 0) {
          ++ans;
        } else {
          --x;
        }
      }
    }
    ans += x << 1;
    return ans;
  }
};

func minInsertions(s string) int {
  ans, x, n := 0, 0, len(s)
  for i := 0; i < n; i++ {
    if s[i] == '(' {
      x++
    } else {
      if i < n-1 && s[i+1] == ')' {
        i++
      } else {
        ans++
      }
      if x == 0 {
        ans++
      } else {
        x--
      }
    }
  }
  ans += x << 1
  return ans
}