1541. Minimum Insertions to Balance a Parentheses String

题目信息

题号:

1541

难度:

Medium

主题:

字符串、括号匹配、贪心

原题:

LeetCode 1541

重点:

每个左括号必须由连续两个右括号匹配;可在任意位置插入括号,求最少插入数

题目重述

给定只包含 ( 和 ) 的字符串 s。在本题的平衡规则中,每个左括号都必须对应其右侧连续出现的两个右括号 )),并且括号嵌套关系必须合法。

可以在字符串任意位置插入左括号或右括号。请返回使字符串满足上述规则所需的最少插入次数。

1 <= s.length <= 10^5。

自建示例

已经由一个左括号和两个右括号组成时无需插入:

输入:s = "())"
输出:0
解释:唯一左括号恰好由连续的两个右括号匹配。

孤立左括号需要补充两个右括号:

输入:s = "("
输出:2
解释:在末尾插入 "))" 后得到平衡字符串。