string · run elimination

消除次序与最短剩余串

给定一个字符串，允许反复执行一种操作：选中一段连续相同的字符（长度不小于 2）删除；删除后左右邻居贴合，可能形成新的连续段，从而继续删除。问题是通过安排消除次序，使最终结果串最短。

次序会改变结果。abbbbccccbd 若从左先删 bbbb，中间落单的 b 再也凑不齐连续段，只能停在 abd；若先清掉隔在中间的 cccc，两侧的 b 就能合并成一段整体删去，可达更短的 ad。本页三节：操作与级联 → 固定次序贪心的失效 → 区间 DP 求最短。

1 · 操作与级联

1.1 · 操作的定义

一次消除操作在当前串中选定一段连续且相同的字符，长度不小于 2，将选定的这一段删除。所选段不必是当前串里的极长段：bbbb 里只删其中两个 b 同样合法。删除与字符个数的奇偶无关，bbbbb 这样的五连段也是一次删空。删除后被删段左右两侧的字符在新串中相邻，若它们恰好相同就构成新的连续段，可以继续被删除。这种连锁称为级联。

放宽到子段是否会得到更短的结果，这一点值得单独验证。穷举 2 字母长 9、3 字母长 8、4 字母长 7 三组共 23457 个串，「可删任意长度不小于 2 的同字符子段」与「只允许整段删极长段」两种模型给出的最短长度完全一致，差异样本为零。本页未找到这个等价性的证明，只有这份穷举证据；core/elim.ts 的实现按前者写。

图 1-1 · 一条能到达最短结果的消除次序，逐段回放。红色为本步删除的段，变灰带删除线的是已删字符（仍占原始位置以便观察两侧贴合），末帧以绿色标出幸存字符。可改输入串换例子。

1.2 · 障碍段与跨越式合并

abbbbccccbd 的位置 1–4 是 bbbb，位置 9 是一个落单的 b，中间隔着 cccc（位置 5–8）。单独看，位置 9 的 b 没有相邻同字符，消不掉。但把中间的 cccc 清空后，位置 4 与位置 9 的两个 b 在新串中相邻，五个 b 连成一段整体删除，只剩位置 0 的 a 与位置 10 的 d，即 ad。级联的价值就在于让原本被障碍段隔开的同字符跨越式合并。

图 1-1 回放的次序与上面这段叙述并不相同。上面为讲清原理，说的是「先清掉 cccc」；而 DP 重建出的次序是 bb(1,2) → cc(5,6) → cc(7,8) → bbb(3,4,9)，先从 bbbb 里删掉两个 b，再分两次清掉 cccc，最后把剩下的三个 b 并成一段。两条次序都到达 ad，长度相同。重建出的是某一条最优次序，取决于 $E$ 枚举配对时的择优策略，不是叙述里那条。

1.3 · 次序的不唯一性

同一个串可能存在多条到达最短的次序，最终结果串也可能不唯一：abbccaabbc 可消到 a 或 c，长度都是 1。需要计算的是最短可达长度与一组对应的幸存字符，这由区间 DP给出。

2 · 固定次序贪心的失效

2.1 · 从左优先的实现

最直接的想法是从左往右扫，遇到的第一个连续段就立刻删掉；删完因左右贴合可能产生新段，需回退一格继续扫，直到再也找不到连续段。

图 2-1 · 从左优先贪心的实现，一个带回退的单趟过程。

它一定会终止，因为每次删除都缩短串；最终落在一个「无任何相邻相同字符」的稳定态。问题在于稳定态不止一个，落在哪个取决于消除次序，而这个贪心把次序写死成了永远先删最左，因此它求到的是某个稳定态，不保证是最短的那个。

穷举可以量出差距有多常见。长 10 的串里，2 字母表有 372/1024（36.3%）的串上贪心严格劣于最优，最大差距 3；3 字母表是 9984/59049（16.9%），最大差距 5。字母表越小贪心越吃亏，这与「字母少更容易消」的直觉相反——字母少意味着连续段更多、次序的选择空间更大，先删哪一段的后果也就更严重。

2.2 · 卡住的那一刻

图 2-2 · 贪心的逐步回放。红色为本步删除的最左连续段，橙色是贪心停下时残留的字符，读数里并列给出最短可达长度。可换预设串对比。

警示 · 反例 abbbbccccbd：贪心从左先删 bbbb，原位置 9 那个落单的 b 就此无法再与任何同字符相邻，停在 abd（长度 3）；而先清掉中间的 cccc、让两侧 b 合并再删，可达 ad（长度 2）。贪心的局部决策废掉了一次本可达成的跨越式合并。

并非所有串都让贪心落入次优。abccbbd 上贪心与最优都得到 ad，长度 2。而 abcabc 根本没有任何长度不小于 2 的连续段，一次操作都做不了，两者都停在原串——这不是「次序无差别」，是没有次序可言。差距只在需要先清障碍段、为远处同字符创造合并机会时才出现。

3 · 区间 DP 求最短

3.1 · 子串可消空性的判定

核心子问题是：子串 $s[i..j]$ 能否被完全消空，记作 $E(i,j)$ 。既然要消空，首字符 $s[i]$ 必须被删，而它一定是作为某个同字符连续段的一员被删的。只需枚举它与后面某个同字符 $s[k]$ 配对：若其间的 $s[i+1..k-1]$ 能消空，这两个字符就会贴成一段；再让这一段继续向右并入更多同字符、整段删除、尾部也消空：

E(i,j) \;=\; \bigvee_{\substack{i < k \le j \\ s[k] = s[i]}} \Big( E(i+1,\,k-1) \;\wedge\; A(k,j) \Big)

其中 $E(i,j)$ 在 $i > j$ 时（空串）取真。

图 3-1 ·

E(i,j)

的可执行版本，与上式逐行对应。

配对之后余下的延展交给辅助态 $A(k,j)$ ：此刻一段同字符已攒到位置 $k$ （段内最右的那个），问 $s[k..j]$ 能否整个消空。两条出路。「停」：这段字符（至少两个）就此整段删除，要求尾部 $E(k+1,j)$ 。「续」：右边还有一个同字符在 $k_2$ ，其间的 $s[k+1..k_2-1]$ 先消空让它并进来，再递归 $A(k_2,j)$ 。

A(k,j) \;=\; E(k+1,\,j) \;\vee\; \bigvee_{\substack{k < k_2 \le j \\ s[k_2] = s[k]}} \Big( E(k+1,\,k_2-1) \;\wedge\; A(k_2,j) \Big)

图 3-2 · 辅助态

A(k,j)

的可执行版本：先试「停」，再枚举向右并入的下一个同字符。

3.2 · 辅助态的消去

$A$ 的第二项与 $E$ 的定义式逐字相同，就是 $E(k,j)$ 。所以 $A$ 不过是 $E$ 多一条「就地停」的出路，代回后辅助态可完全消去，判定只剩 $E$ 自身：

E(i,j) \;=\; \bigvee_{\substack{i < k \le j \\ s[k] = s[i]}} \Big( E(i+1,\,k-1) \;\wedge\; \big( E(k,j) \vee E(k+1,j) \big) \Big)

图 3-3 · 消去辅助态后的纯

E

自递归，与图 3-1、图 3-2 那一对在所有子区间上给出相同判定。

注 · 记号 $\exists k \in (i, j]$ 读作「存在某个下标 $k$ ，取值 $i < k \le j$ 」， $\exists$ 是存在量词， $(i, j]$ 是左开右闭区间， $i$ 不取而 $j$ 取。整行即代码里「只要循环中找到一个满足条件的 $k$ 就返回 true」的数学写法。与之相对的全称量词 $\forall$ 读作「对所有」，表示条件对范围内每个元素都成立，本页未用到。

core/elim.ts 里仍单独保留了 $A$ ，不是判定需要，而是为了记录每步是「停」还是延展到哪个锚点，供图 1-1 重建删除次序。

按子串长度从小到大填表即可得到全部 $E(i,j)$ 。表里同一区间可能有多个字符被并入同一连续段，锚点链因此可以长于两个：aaa 的 $E(0,2)$ 锚点是位置 0、1、2 三个，abbacca 的 $E(0,6)$ 是 0、3、6。

图 3-4 · 按子串长度递增填

E

的三角表，✓ 为可消空、✗ 为消不空。上方字符高亮当前判定的区间，红色为并入同一连续段的全部锚点。

3.3 · 判定之上的最短化

有了 $E$ ，最短化就清楚了。从左到右，每个字符要么作为幸存者保留（计 1），要么属于某个被整体删除的可消空段。幸存者会挡住消除——任意一段的消空只能靠段内字符独立完成，所以保留字符之间的每一段都必须可消空：

F(i) \;=\; \min \Big( 1 + F(i+1), \;\; \min_{\substack{i \le k \le n-1 \\ E(i,k)}} F(k+1) \Big)

图 3-5 · 在判定表之上求最短的

F

，返回最短长度与一组幸存字符位置。

复杂度： $E$ 的子区间状态共 $O(n^2)$ ，每个状态枚举 $O(n)$ 个配对位置，整体 $O(n^3)$ 时间、 $O(n^2)$ 空间。 $F$ 虽然在实现里写成二维 $F(i,j)$ ，但从 $F(0, n-1)$ 出发的两处递归都原样传递 $j$ ，第二维恒为 $n-1$ ，实际只有 $O(n)$ 个状态、每个 $O(n)$ 转移，故 $F$ 一层是 $O(n^2)$ 。

判定表覆盖全部 $O(n^2)$ 个子区间，一次性回答了「任意子串能否消空」。这既支撑了 $F$ 的最短化，也解释了单趟贪心为何不可能等价：贪心无法预见「先清掉某个障碍段会让远处变得可消空」这类跨区间的依赖。

4 · 参考文献

本页的问题是 Clickomania（又名 SameGame）限制在单列时的形态，判定「整串能否消空」即该文献中的可解性问题。Biedl 等人证明单列情形两色可在线性时间内解决、任意色数可在多项式时间内解决，而两列五色或五列三色的可解性判定即为 NP 完全 [1]。本页在可消空性判定之上求最短剩余，是同一判定的优化版本。

Biedl, T. C., Demaine, E. D., Demaine, M. L., Fleischer, R., Jacobsen, L., & Munro, J. I. (2002). The complexity of Clickomania. In R. J. Nowakowski (Ed.), More Games of No Chance (pp. 389–404). Cambridge University Press.