Meta 一维消消乐：相邻重复段与连锁消除

题目重点：不断删除相邻重复字符段，直到不能再消除，明确消除次序、大小写与栈的不变量。

题意与假设

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

训练采用每次删除最左侧长度>=2的最大等字符段，大小写敏感；不是长度>=3的另一类Candy Crush。
选择最左顺序是明确训练约定，题目若要求全部重复段同步删除，需改为同步轮次算法。aabbba最左策略结果a，同步首轮也为a，而先删中间bbb会得到空串，说明任意挑段并不等价。

解题路线

按最大等字符run读入，用栈保存尚未最终确定的段。栈内除顶段外都已经是不能消除的单字符；新不同字符到来时，顶段若count>=2才完整弹掉。
弹掉顶段后，新段可能与前一段字符相同，合并count；否则push新段。此时不急着消掉新形成的重复段，等下一个不同字符确定其完整范围，再按最左顺序删除。
输入结束后处理顶段；结果其余段均不可消除。每段至多入栈一次、弹一次，避免每轮从头扫描字符串的O(n²)基线。
若同步规则，第一轮应依据同一轮开始前的所有段同时删，之后再找新段；局部贪心可能给不同结果，应用明确oracle验证。

手动走一遍

abbba先删bbb得到aa，再删aa得到空串。Acbcccbac先删ccc得Acbbac，再删bb得Acac；A与a不同，不能把结果偷偷变为acac。

Python 参考实现

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

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

from itertools import groupby


def crush_leftmost(text):
    """Repeatedly remove the LEFTMOST maximal equal-character run of length >=2.

    Case-sensitive; no lowercasing. A new boundary can create another removable run.
    """
    stack=[]
    for char,group in groupby(text):
        count=sum(1 for _ in group)
        if stack and stack[-1][0] != char and stack[-1][1]>=2:
            stack.pop()
        if stack and stack[-1][0]==char:
            stack[-1][1]+=count
        else:
            stack.append([char,count])
    if stack and stack[-1][1]>=2:
        stack.pop()
    return ''.join(char*count for char,count in stack)

复杂度

O(n)时间/O(n)最坏栈与输出空间；groupby读取每字符一次，段count可累积。独立测试按最左段逐轮直接删除核对，而不是复制栈逻辑。

易错点与追问

容易失分的边界

看到第二个相同字符就立即删，会错误处理长度3及以上完整段；需先明确最大run结束。
忽略大小写会改变题面字符相等关系。

继续深挖

门槛改为>=k时，顶段到边界再判断count>=k；若规则是每k个删而长段留余数，则不是同一个run模型。
若输出每轮变化，数量与文字复制可能O(n²)，不能仍宣称包含全轨迹输出线性。