Meta 最少删除无效括号：原地两遍与空间口径

题目重点：保留普通文字，只删除最少数量的圆括号，并实现可变字符数组上的常数辅助空间。

题意与假设

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

训练只匹配()，其他字符原样保留；返回任意最少删除结果，不要求最短字典序。示例输入为可变list并返回同一list。
若输入是不可变字符串，创建字符数组和返回字符串需要O(n)空间；不能把Python字符串包装版本标为总空间O(1)。

解题路线

从左向右记录balance并用write压缩保留字符。遇到)且balance0，这个右括号没有任何左侧可匹配开括号，必须删除；其他字符写入，保留普通文字。
第一遍后所有前缀不再负数，但balance个多余(还未匹配。从右向左删除恰好balance个(，其余字符向右压缩，最后去掉前面空隙。
为何删最右侧多余开括号可行？第一遍已配对的闭括号可以重新匹配更早保留的开括号；删最右balance个不会使任一前缀缺开括号。也可用反向匹配计数推导同样结果。
最少性来自两类无法配对项：第一遍每个缺前置(的)都必须删，剩余净多余(也必须删。算法恰好删这些数量，因此没有删任何必要以外字符。
原地写指针方向与读取方向一致，避免覆盖未读字符；反向阶段也只写到当前位置或右侧。通过裁剪列表长度返回，不构造第二个字符数组。

手动走一遍

a)b(c)d第一遍删第一个)，得到ab(c)d且balance0；((a)第一遍balance1，反向删除最右未必要保留的(，得到(a)。((只剩空串，普通a不能删除来减少长度。

Python 参考实现

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

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

def remove_unbalanced_inplace(chars):
    """Mutable character list; keep other text, delete minimum parentheses.

    Returns the same list, O(1) algorithmic auxiliary storage. A string wrapper
    would need O(n) for conversion/output. Input is modified.
    """
    write=0;balance=0
    for read in range(len(chars)):
        ch=chars[read]
        if ch=='(':
            balance+=1
        elif ch==')':
            if balance==0:continue
            balance-=1
        chars[write]=ch;write+=1
    del chars[write:]
    write=len(chars)-1
    for read in range(len(chars)-1,-1,-1):
        if chars[read]=='(' and balance:
            balance-=1;continue
        chars[write]=chars[read];write-=1
    del chars[:write+1]
    return chars

复杂度

O(n)时间、O(1)算法辅助空间，结果保存在输入数组；Python list裁剪的内部内存管理不等于新建完整输出副本。字符串接口若先list(text)再join，总分配仍O(n)，返回输出长度单独说明。

易错点与追问

容易失分的边界

只删负前缀右括号，未处理尾部多余左括号。
从左边任意删多余(可能破坏前缀匹配，反向或计数预算有证明才安全。

继续深挖

如果要求保留最早开括号，当前反向删除如何满足？若要求另一tie政策要调整选择。
三类括号不能用一个balance计数直接复用本算法，嵌套类型顺序必须保留。