Question

1541. Minimum Insertions to Balance a Parentheses String

中文文档

Description

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 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.

Solutions

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