921.使括号有效的最少添加

使括号有效的最少添加

只有满足下面几点之一，括号字符串才是有效的：

• 它是一个空字符串，或者
• 它可以被写成 AB（A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
• 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s ，移动 N 次，你就可以在字符串的任何位置插入一个括号。

返回 为使结果字符串 s 有效而必须添加的括号的最少数量。

示例 1：

输入：s = “())”
输出：1

示例 2：

输入：s = “(((“
输出：3

提示：

• 1 <= s.length <= 1000
• s 只包含 ‘(‘ 和 ‘)’ 字符

解析

使用贪心，维护需要匹配的左括号数量和需要添加的右括号数量。

var minAddToMakeValid = function (s) {
  let leftNeed = 0;
  let rightNeed = 0;

  for (const c of s) {
    if (c === "(") {
      leftNeed++;
    } else {
      if (leftNeed > 0) {
        leftNeed--;
      } else {
        rightNeed++;
      }
    }
  }

  return leftNeed + rightNeed;
};

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