算法标签

贪心策略、字符串去重、单调性优化

问题分析

本题要求对二进制串执行DRY压缩算法，通过反复删除连续重复的子串，得到最短的最终字符串。核心是利用二进制串仅含0和1的特性，简化压缩逻辑，找到最优压缩路径。

关键观察

1. 二进制串的特殊性：二进制串只有0和1两种字符，连续重复的子串本质上是由交替出现的0和1构成的片段（如“11”“00”“1010”等）。
2. 最优压缩的核心：重复删除连续重复子串后，最终最短字符串的长度不会超过3。因为长度≥4的二进制串必然包含可删除的连续重复子串（如“0011”可删“00”或“11”，“0101”可删“01”）。
3. 预处理去重：先将原串中连续相同的字符合并（如“1111”合并为“1”，“10110”合并为“1010”），这一步不改变压缩的最优结果，却能大幅简化后续处理。

核心算法思路

1. 连续字符合并

遍历原字符串，将连续相同的字符合并为单个字符（如“1110011”→“101”），得到简化后的字符串onh。这一步能快速消除最基础的连续重复（长度为2的重复子串）。

2. 长度截断优化

由于合并后的字符串onh是0和1交替出现的序列，其长度若≥4，必然存在可进一步删除的连续重复子串。因此直接将长度≥4的onh截断为前（长度-2）个字符，最终保留长度≤3的字符串，即为最短结果。

3. 结果输出

截断后的字符串即为最优压缩结果，无需进一步迭代删除，因为长度≤3的交替二进制串（如“010”“101”“01”）不存在连续重复子串，无法再压缩。

复杂度分析

• 时间复杂度：$O(N)$，其中$N$为原字符串长度。仅需一次遍历完成连续字符合并，后续截断操作为$O(1)$，效率极高，可满足$N \leq 10^5$的要求。
• 空间复杂度：$O(N)$，用于存储合并后的字符串onh，最坏情况下（原串无连续相同字符）与原串长度一致。

总结

本题的关键是利用二进制串“仅含0和1”的特性，发现最优压缩结果的长度上限为3。通过“连续字符合并+长度截断”的贪心策略，无需复杂的重复子串查找与迭代删除，即可高效得到最短字符串。核心思路是抓住问题本质，用预处理和性质推导简化求解过程，避免冗余计算。