本文深入剖析“递归移除字符串中所有相邻重复字符”算法的真实时间复杂度，澄清常见误解，通过代码结构与执行轨迹论证其整体时间复杂度为线性 o(n)，而非误传的 o(n²)。
本文深入剖析“递归移除字符串中所有相邻重复字符”算法的真实时间复杂度，澄清常见误解，通过代码结构与执行轨迹论证其整体时间复杂度为线性 o(n)，而非误传的 o(n²)。
该问题的核心在于理解 rremove 函数中循环调用 solve 的实际行为——它并非“逐对消除、多次迭代”，而是一次性扫描并移除所有当前存在的连续重复段，且最多只需两次调用即可收敛。
我们先观察 solve 方法的逻辑：
- 它使用单指针 i 从左到右遍历字符串；
- 遇到 s[i] == s[i+1] 时，内层 while 快速跳过整个连续相同字符块（例如 "aaaa" 中，i 会从 0 直接跳到 3，再执行 i++ 后进入下一位置）；
- 否则将当前字符追加至 ans；
- 整个过程仅遍历原字符串一次，时间复杂度为 O(|s|)，空间复杂度为 O(|s|)（用于构建新字符串）。
关键误区在于误读 rremove 的 while 循环：
String s1 = "";
while (s1.length() != s.length()) {
s1 = s;
s = solve(s); // 注意：solve 移除的是「所有当前可识别的相邻重复对」
}表面上看是“反复调用直到稳定”，但需注意：
✅ solve 并非只删除一对相邻重复（如 "aabb" → "bb" → ""），而是一次性清除所有长度 ≥ 2 的连续重复段的首尾重叠部分。
✅ 更重要的是：该循环最多执行 2 轮。原因如下：
- 第一轮 solve(s)：移除所有形如 "aa", "bbb", "cccc" 等连续重复块的「内部冗余」，生成一个无相邻相同字符的字符串（即满足 s[i] ≠ s[i+1] 对所有有效 i 成立）——记作 s'。
- 此时若 s' 中仍存在新形成的相邻重复（如 "abccba" 经第一轮变为 "abba"，再变为 "aa"，最后变为空），那说明原字符串存在嵌套/间接重复结构。但仔细分析 solve 行为可知：它在单次扫描中已合并所有连续相同字符为单个字符（如 "ccc" → "c"），因此不可能因删除中间字符而“暴露”出新的相邻重复。
❌ 反例 "abccba" 的错误假设源于对 solve 的误读：solve("abccba") 执行过程如下：
a→保留；b→保留；c,c→跳过第二个 c；接着 c,b→c 保留；b,b→跳过第二个 b；b,a→b 保留 → 结果为 "abca"（不是 "abba"）。
✅ 正确结论：solve 是贪心压缩操作，等价于正则替换 "(.)\1+" → "$1"，单次调用即可得到最终稳定结果。因此 rremove 中的 while 循环实际只会执行 1 次（当输入已稳定）或 2 次（极少数边界下首次未完全收敛，但第二轮必收敛），属于常数级开销。
综上，设输入长度为 n：
- 每轮 solve 耗时 O(n), O(n−1), O(n−2)... 递减；
- 总时间 ≤ O(n) + O(n) = O(n)；
- 严格来说，最坏情况也是 O(n)，与输入规模呈线性关系。
? 注意事项：
- 该算法不满足“递归”字面含义（无函数自调用），实际是迭代收缩，命名 rremove 易引发混淆；
- 若改用栈模拟（如 LeetCode 1047），可实现真正单次 O(n) 且空间更优（O(n) 时间 + O(n) 栈空间）；
- 实际工程中建议使用 StringBuilder 复用或栈方案，避免频繁字符串创建带来的隐式开销。
总结：本题时间复杂度确为 O(n)，所谓 O(n²) 的说法源于对 solve 功能的误判（当成每次仅删一对）及对循环次数的过度悲观估计。掌握扫描压缩的本质逻辑，是准确分析此类字符串规约算法复杂度的关键。
