递归移除所有相邻重复项的时间复杂度分析求助

先明确两段核心代码的功能：

• solve方法：遍历字符串，移除所有连续重复的字符块（只要有连续重复的字符，整个连续块都不保留），只保留无连续重复的单个字符。
• rremove方法：循环调用solve，直到字符串长度不再变化（即字符串中已无连续重复字符，或为空）。

1. solve方法的时间复杂度 #

solve是线性遍历，时间复杂度为O(k)，其中k是输入字符串的长度。

• 外层while循环的i从0递增到k-1，内层while仅用于跳过连续重复的字符，不会重复处理已经扫描过的字符。
• 每个字符最多被访问一次，整个过程是线性的。

2. rremove方法的时间复杂度 #

rremove循环调用solve，但总处理的字符数总和是O(n)（n为初始字符串长度），原因如下：

• 每次调用solve后，字符串中所有连续重复的字符块都会被移除，剩余字符串中的字符要么是无连续重复的，要么是新形成的连续重复块（比如"abba"处理后变成"aa"）。
• 每个字符最多会被solve扫描两次：第一次在原始字符串中，第二次在新形成的连续重复块中，之后就会被移除。
• 总扫描的字符数不会超过2n，因此整体时间复杂度是O(n)。

为什么有些资料说是O(n²)？ #

这种误解通常来自混淆了逐个移除相邻重复对的暴力解法（比如每次扫描仅移除一对相邻重复字符），那种解法最坏情况会出现O(n²)的时间复杂度。但你的代码中solve是一次扫描移除所有连续重复块，效率更高，不存在O(n²)的情况。

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