递归移除字符串相邻重复项的时间复杂度分析

先明确这段代码的核心逻辑：每次遍历字符串时，会一次性移除所有连续重复的字符块（只要有连续重复就整段跳过）；如果处理后的字符串和原字符串不同，就递归处理新字符串。下面分情况分析时间复杂度：

最优情况 #

• 时间复杂度：O(n)
• 适用场景：
  • 原字符串本身没有任何相邻重复字符（例如"abcdef"）：第一次遍历后生成的结果和原字符串完全一致，不会触发递归，仅需一次O(n)的遍历。
  • 原字符串的所有连续重复块被移除后直接得到空字符串（例如"aabbcc"）：仅需两次遍历（原字符串长度n + 空字符串长度0），总时间仍为O(n)。

最坏情况 #

• 时间复杂度：O(n)
• 适用场景：每次递归处理后会产生新的连续重复字符，需要多次递归，但总遍历的字符数仍为线性级别。
  举个例子，输入字符串为"abbaabba"：
  1. 第一次遍历处理原字符串，移除中间的"bb"和"bb"块，得到"aaaa"，遍历长度为8；
  2. 第二次遍历处理"aaaa"，移除整个连续块得到空字符串，遍历长度为4；
  3. 第三次遍历空字符串，直接返回，遍历长度为0。
     总遍历长度为8+4=12，对应原字符串长度n=8，仍为O(n)级别。

为什么最坏情况不是O(n²)？ #

因为每个字符最多会被遍历两次：要么在某次遍历中被直接移除，要么被保留到下一次递归的字符串中，之后被移除或保留到最终结果。所有递归调用的遍历字符总数是O(n)，因此总时间复杂度始终是线性的，不会出现平方级别的增长。

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