Meta 最少补括号：无法匹配的闭括号与剩余开括号

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 字符串只包含()，允许任意位置插入单个(或)，只返回最少插入次数；空串0。不是每个(必须配两个)的变体。

解题路线

1. opened记录尚未匹配的开括号数。遇(加1，遇)且opened>0则匹配一个；否则这个)前必须补一个(，added加1。
2. 扫描末尾opened个剩余开括号各需要补一个)，答案added+opened。每次缺配对都至少要一次插入，算法提供恰好这么多的构造，所以最优。
3. 不得遇负前缀后仅把counter变负再最后abs求答案：后续开括号不能补到此前闭括号前面。prefix缺口与suffix剩余必须分别记录。
4. 如需返回实际补后字符串，缺匹配)前插(，末尾追加opened个)，但输出可能接近2n，空间不再是只求次数的常数。

手动走一遍

))((前两个)各补(，最后两个(各补)，总4；())得到1，(()得到1，()()为0。只看净balance的绝对值会把))((误判为0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def minimum_additions(text):
    """Input only '(' and ')', insert single parentheses to balance."""
    opened=0;added=0
    for ch in text:
        if ch=='(':opened+=1
        elif ch==')':
            if opened:opened-=1
            else:added+=1
        else:raise ValueError('parentheses only')
    return added+opened

复杂度

O(n)时间/O(1)辅助空间；若构造输出O(n+answer)输出长度和空间。字符非法时明确拒绝而不自动忽略，因为本合同不是混合文本。

易错点与追问

容易失分的边界

• 把净balance归零当作有效，遗漏前缀条件。
• 混用双闭括号规则会给出不同答案。

继续深挖

• 如果一次可以插入一对括号而不是单字符，最优代价如何定义？
• 若允许同时替换/删除，计数贪心是否还足够？应重新建立操作成本。