本文澄清一个常见误解：对“递归调用 solve 移除所有相邻重复字符”的算法，其真实时间复杂度为线性 O(n)，而非部分资料误判的 O(n²)，关键在于 solve 函数单次即可消除全部相邻重复段，且外层循环最多执行一次。
本文澄清一个常见误解：对“递归调用 `solve` 移除所有相邻重复字符”的算法，其真实时间复杂度为线性 o(n)，而非部分资料误判的 o(n²)，关键在于 `solve` 函数单次即可消除全部相邻重复段，且外层循环最多执行一次。
该问题的核心在于理解 rremove 方法中 while 循环的实际执行次数——它并非按字符数量或轮次线性增长，而是具有强收敛性：至多执行 1 次完整迭代。
我们来逐步分析：
✅ solve 函数：单趟扫描，O(n) 完成全局去重
solve 并非“每次只删一对相邻重复”，而是采用贪心跳过策略：
- 遍历字符串时，一旦发现 s[i] == s[i+1]，就持续向后滑动 i，跳过整个连续重复段（例如 "aaabbbcc" 中的 "aaa" 会被一次性跳过）；
- 仅将每个连续段的首个字符之外的所有字符跳过，而首个字符也不保留（因后续必然与前一不同段分隔），真正追加的是所有非重复起始位的孤立字符；
- 更重要的是：该实现实际完成的是「移除所有长度 ≥ 2 的连续重复子串的首尾重叠部分」，等价于标准的「相邻重复消除」（如 "abbaca" → "ca"）。虽然代码逻辑略隐晦，但效果是：一轮 solve 就能消除所有当前存在的相邻重复对，并可能暴露出新的相邻关系（如 "aabba" → "a"）。
? 示例验证：
输入 "abbbaca"
- 第一趟 solve：
- i=0: 'a'≠'b' → append 'a'
- i=1: 'b'=='b' → 跳过 i=1,2（覆盖 "bbb"），i 最终停在 3；接着 i++ 后为 4
- i=4: 'a'=='a' → 跳过 i=4，i 停在 5；i++ 后为 6
- i=6: 'c'≠'a' → append 'c'；最后 append 'a'
→ 得 "aca"- 第二趟 solve("aca")：无相邻重复 → 输出 "aca"，与输入等长 ⇒ 循环终止
仅调用 2 次 solve，且每次均为 O(n)
✅ 外层 rremove 循环：最多执行 1 次有效迭代
关键观察：
- 字符串长度严格单调递减（除非已无重复，此时 s1.length() == s.length() 立即退出）；
- 每次 solve(s) 至少消除 ≥ 2 个字符（因至少存在一对相邻重复才会进入内层 while）；
- 但更重要的是：不可能出现“消除一部分 → 新重复 → 再消除一部分 → ……反复 n 次”的链式场景。
实际上，solve 的扫描机制保证了：所有因前序删除而新暴露的相邻字符，会在同一趟扫描中被识别并处理（因其基于原始索引顺序、无回溯，但通过跳过逻辑隐含了“批量坍缩”效果）。形式化证明可借助「势函数」：定义势 Φ(s) = 字符串中相邻相等位置对的数量，则每趟 solve 至少减少 Φ，且 Φ ≤ n−1，故总迭代数 ≤ n；但实践中，由于消除是成块发生的，典型输入下 Φ 快速归零 —— 经验与理论均支持最坏情况仍为 O(1) 次调用。
因此，总时间复杂度 = solve 调用次数 × 单次 solve 复杂度 = O(1) × O(n) = O(n)。
⚠️ 注意事项与常见误区
- ❌ 误区：“solve 每次只删一对，所以要调用 O(n) 轮” → 错。本实现中 solve 是全量扫描器，不是单步消重器；
- ✅ 正确理解：solve 的 while(i 跳过整个连续重复块，而非逐对处理；
- ? 优化提示：当前 rremove 使用字符串比较 s1.length() != s.length() 判定收敛，虽简洁，但若需更高鲁棒性，可改用 !s1.equals(s)（避免长度相同但内容不同的巧合）；
- ? 空间复杂度：StringBuilder 为 O(n)，无递归栈，故总空间为 O(n)。
✅ 总结
该算法的时间复杂度确为 O(n)，主因是 solve 函数具备“单趟全局消重”能力，且外层收敛极快。所谓 O(n²) 的判断，源于对 solve 行为的误读（将其当作朴素的一对一删除）。掌握扫描类双指针/跳过式遍历的“批量处理”本质，是准确分析此类问题的关键。
