本文深入剖析“递归移除字符串中所有相邻重复字符”算法的真实时间复杂度，通过代码逻辑拆解与执行轨迹分析，证明其整体复杂度为线性 o(n)，而非被误传的 o(n²)，并指出错误归因的关键所在。
本文深入剖析“递归移除字符串中所有相邻重复字符”算法的真实时间复杂度，通过代码逻辑拆解与执行轨迹分析，证明其整体复杂度为线性 o(n)，而非被误传的 o(n²)，并指出错误归因的关键所在。
该问题的核心实现包含两个关键方法：solve()（单轮扫描去重）和 rremove()（外层循环调用直到无变化）。表面上看，rremove() 中存在 while(s1.length() != s.length()) 循环，容易让人直觉认为最多执行 O(n) 轮、每轮 O(n)，从而得出 O(n²) 的结论。但这一判断忽略了 solve() 方法的全局消融特性——它并非每次仅删除一对相邻重复字符，而是在一次遍历中识别并跳过所有连续重复段，仅保留每个重复段的首个字符（实际逻辑是：遇到重复对即跳过全部连续相同字符，不添加任何字符；否则才追加当前字符）。
我们来重审 solve() 的核心逻辑：
String solve(String s) {
StringBuilder ans = new StringBuilder();
int i = 0;
while (i < s.length()) {
// 若当前字符与下一个字符相同，则跳过整个连续重复段
if (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
char c = s.charAt(i);
while (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
i++; // 跳过所有后续相同字符
}
i++; // 再跳过最后一个相同字符（避免重复处理）
} else {
ans.append(s.charAt(i)); // 仅保留非重复位置的字符
i++;
}
}
return ans.toString();
}⚠️ 注意：原代码中 i++ 在 if 分支末尾缺失，导致逻辑缺陷（会重复处理或越界）。上述修复版明确体现其单轮清除所有连续重复块的能力：例如输入 "aaabbbcc"，solve() 将直接输出 ""（全被跳过），而非 "abbc"；输入 "abccba" 则输出 "abba" —— 即一轮即完成所有可消除的相邻重复对的首次处理。
更重要的是，rremove() 的终止条件 s1.length() != s.length() 实质检查字符串是否发生变更。关键洞察在于：每一次 solve() 调用，都会严格缩短字符串长度（除非已无相邻重复）。由于字符串初始长度为 n，且每次调用至少删除 ≥2 个字符（如 "aa" → 删除 2 字符），因此 solve() 最多被调用 ⌊n/2⌋ 次？—— 这仍是表面推理。
但深入观察消融机制：solve() 并非简单“删一对”，而是在单次扫描中合并所有连续重复段，并只保留每个段的「边界效应」字符。更准确地说，该算法等价于模拟栈式消除（如 LeetCode 1047），但此处实现为贪心跳过。实际上，在最坏情况下（如 "ababab..."），solve() 可能不删除任何字符；而在最佳消除链式场景（如 "aabbcc..."），一轮即可清空。然而，无论输入如何，solve() 的每次调用都是 O(n) 时间，且总调用次数被严格限制为常数级（至多 1 次有效消除）——因为 solve() 本身已具备「完全消除本轮所有可触达相邻重复」的能力，后续调用仅在前次结果仍含新生成的相邻重复时发生（例如 "abccba" → "abba" → "aa" → ""）。但注意：这种链式产生新相邻对的情况，最多发生 O(log n) 层（类似归并深度），而非 O(n)。
✅ 正确结论：
- 单次 solve(s) 时间复杂度为 O(|s|)，因其仅遍历字符串一次；
- rremove() 中 solve() 的调用次数在最坏情况下为 O(log n)（由重复消除引发的“新邻接”呈指数衰减），故总体时间复杂度为 O(n)；
- 常见 O(n²) 误判源于将 solve() 错误理解为“每次仅删 1 对”，忽视了其内层 while 循环对连续段的整体跳过能力。
? 总结建议：
- 分析递归/迭代消除类算法时，应聚焦「每轮操作的实际消除量」，而非仅看外层循环结构；
- 使用 StringBuilder 和单指针扫描是高效实践，但需确保边界逻辑完备（如修复原代码中缺失的 i++）；
- 若追求更清晰的 O(n) 保证，推荐改用显式栈实现（逐字符压栈，遇栈顶匹配则弹出），其时间与空间复杂度均严格线性且易于验证。
