如何在≥3字符匹配约束下移除字符串连续重复字符以得到最小结果？

这问题挺有意思的——不同的移除顺序居然会带来完全不同的最终结果，要拿到字典序最小的字符串，得选对移除的优先级才行。

核心思路：以最终字典序为导向 #

我们的目标是让最终字符串的字典序尽可能小，而字典序的比较规则是从左到右逐个字符对比：越早出现更小的字符，整个字符串就越小；如果前面的字符完全相同，短字符串比长字符串更小。所以所有操作决策都要围绕这个目标来做。

最优操作策略 #

这里给一套能确保得到最优解的方法，逻辑清晰且可落地：

• 第一步：扫描当前字符串，找出所有长度≥3的连续重复字符段（也就是所有可移除的目标）。
• 第二步：对每个可移除的段，模拟移除它之后，继续按照同样规则处理新生成的字符串，直到没有可移除的段为止，记录下每个选择对应的最终结果。
• 第三步：从所有模拟得到的最终结果中，选出字典序最小的那个，对应的初始移除操作就是我们当前该做的选择。
• 第四步：重复上述步骤，直到字符串中没有可移除的段为止。

用题目示例验证 #

拿输入字符串AAAABBBAC来实际走一遍：

1. 初始状态下，可移除的段有两个：AAAA（位置0-3，字符A）和BBB（位置4-6，字符B）。
2. 分别模拟两种移除选择：
   • 选择移除AAAA：得到新字符串BBBAC，此时可移除段是BBB，移除后得到AC，这就是最终结果。
   • 选择移除BBB：得到新字符串AAAAAC，此时可移除段是AAAAA，移除后得到C，这是另一个最终结果。
3. 比较AC和C的字典序：第一个字符A的ASCII码（65）小于C的ASCII码（67），所以AC的字典序更小。因此我们应该优先选择移除AAAA段，最终得到AC。

补充：简化判断的小技巧 #

如果不想每次都完整模拟（尤其是字符串很长的时候），可以先做一些快速判断：

• 优先移除包含更小字符的可移除段：比如如果有A段和B段可选，先移除A段，因为A的字典序更小，移除后可能让更小的字符保留在前面。
• 如果多个可移除段的字符相同，优先移除最左侧的段：这样能尽早消除左侧的重复，避免后续合并出更大的段影响结果。
• 特殊情况需权衡：如果移除某个小字符段后，会导致后续更大的字符无法被消除，而移除大字符段后能消除更多大字符，这种情况下还是得靠模拟来确认最终结果的优劣。

内容的提问来源于stack exchange，提问作者Anisotropic