安排消除次序，求最短结果

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

例如 abbbbccccbd：若从左贪心先删 bbbb，中间落单的 b 再也凑不齐连续段，只能停在 abd；但若先删中间的 cccc，左右两段 b 合并成 bbbbb 再整段删去，就能到达更短的 ad。次序决定了能否制造出这种跨越式合并，这正是问题的难点，也是贪心失效、需要区间 DP 全局判定的原因。三步：操作与级联 → 贪心为什么不够 → 区间 DP 求最短。

1 · 操作与级联

1.1 · 操作定义

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

因此「删谁、先删谁」会改变后续能形成哪些连续段。下面单步回放一条能到达最短结果的消除次序：红色为本步选中、即将整段删除的连续段；变灰（删除线）的是已删字符，它仍占据原始位置以便观察两侧如何贴合；绿色为最终保留的幸存字符。

1.2 · 为什么「先删中间」能更短

以 abbbbccccbd 为例：位置 1–4 是 bbbb，位置 9 是一个落单的 b，中间隔着 cccc（位置 5–8）。单独看，位置 9 的 b 没有相邻同字符，消不掉。但只要先删去中间的 cccc，位置 4 的 b 与位置 9 的 b 在新串中相邻，五个 b 连成 bbbbb，整段删除后只剩位置 0 的 a 与位置 10 的 d → ad。

1.3 · 顺序不是唯一，最短长度才是目标

同一个串可能存在多条到达最短的次序，最终结果也可能不唯一（如 abbccaabbc 可消到 a 或 c，长度都是 1）。本节只演示其中一条；真正需要计算的是最短可达长度与一组对应的幸存字符，这由区间 DP给出。

2 · 贪心为什么不够

2.1 · 一个固定次序的贪心

最直接的想法：从左往右扫，遇到的第一个连续段就立刻删掉，删完因为左右贴合可能产生新段，于是回退一格继续扫，直到再也找不到连续段。下面是它的典型实现——一个单趟（带回退）的过程：

它一定会终止（每次删除都缩短串），也不会出错地崩溃，最终落在一个「无任何相邻相同字符」的稳定态。问题在于：稳定态不止一个，落在哪个取决于消除次序，而这个贪心把次序写死成了「永远先删最左」——所以它求到的是某个稳定态，而非最短的那个。

2.2 · 逐步重现它卡住的那一刻

红色为本步删除的最左连续段；播放到最后，橙色是贪心停下时残留的字符。对照下方读数里的「最短可达」即可看出差距。

并非所有串都让贪心落入次优——abccbbd、abcabc 两种次序无差别，贪心也能拿到最短。差距只在「需要先消除障碍段、为远处同字符创造合并机会」时出现。要稳定拿到最短，得放弃固定次序，改用区间 DP 全局判定。

3 · 区间 DP 求最短

3.1 · 可消空判定 E(i,j)

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

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

其实 A 的循环体（const c = s[k] 往下）与 E 的循环体逐字相同，就是 E(k,j)。所以 A 不过是 E 多一条「就地停」；代回后辅助态可完全消去，判定只剩 E 自身：

实现里(core/elim.ts)仍单独保留 A，只为记录每步是「停」还是延展到哪个锚点(aK)，供回放删除次序；纯可消空判定层面 A 如上可消去。

单步填表：按子串长度从小到大判定每个 $s[i..j]$。三角表里 ✓ 表示可消空、✗ 表示消不空；上方字符带高亮当前判定的区间，红色为配对成功的两个 c 锚点。

3.2 · 在判定之上求最短 F

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

复杂度：E 的所有子区间状态共 $O(n^2)$，配上辅助态 A 的转移，整体 $O(n^3)$ 时间、$O(n^2)$ 空间；F 在其上为 $O(n^2)$。填满判定表后，本节直接给出最短结果与一组幸存字符（绿色）。结果可能不唯一，长度才是目标。