如何优化相邻重复字符替换为下一个字母的Python函数性能？

问题背景 #

需求为：遍历仅包含小写字母a-z的字符串，找到第一对相邻重复字符，将其替换为字母表中的下一个字符（若为"zz"则循环替换为"a"），重复此操作直到字符串中无相邻重复字符。例如输入s='aabbbc'，处理流程为：aabbbc → bbbbc → cbbc → ccc → dc，最终返回dc。

现有Python实现（如下）在处理长字符串（如s = 'ab'*10**4 + 'cc'*10**4 + 'dd'*10**4）时性能严重不足。

def solve(s):
    i = 1
    while i < len(s):
        if s[i] == s[i-1]:
            r = s[i+1:]
            l = s[:i-1]
            if s[i] == "z":
                x = "a"
            else:
                x = chr(ord(s[i])+1)
            i = 1
            s = l+x+r
        else:
            i += 1
    return s

原代码性能瓶颈分析 #

1. 字符串频繁拼接：Python中字符串是不可变类型，每次执行s = l+x+r都会生成新的字符串对象，单次拼接时间复杂度为O(n)，多次拼接后整体时间复杂度变为O(n²)，长字符串下开销极大。
2. 重复遍历：每次替换后都从i=1重新扫描整个字符串，前面已经处理过的无重复部分被反复检查，浪费大量计算资源。

优化方案：基于栈的线性时间实现 #

使用栈结构可以高效处理这种需要回溯的场景，仅需一次遍历即可完成所有处理，时间复杂度为O(n)，空间复杂度为O(n)（最坏情况）。

核心思路 #

• 遍历字符串中的每个字符，与栈顶元素对比：
  • 若当前字符与栈顶元素重复，则弹出栈顶元素，计算替换后的字符，然后循环检查新的字符是否与栈顶元素重复（因为替换后的字符可能与前面的元素形成新的相邻重复）。
  • 若不重复，则将当前字符压入栈中。
• 最终将栈中元素拼接为结果字符串。

优化后代码 #

def solve_optimized(s):
    stack = []
    for char in s:
        # 循环检查当前字符与栈顶是否重复，处理替换后的连锁重复
        while stack and stack[-1] == char:
            stack.pop()
            # 计算替换后的字符，z循环为a
            char = 'a' if char == 'z' else chr(ord(char) + 1)
        stack.append(char)
    return ''.join(stack)

优势说明 #

• 避免字符串拼接开销：栈的压入、弹出操作均为O(1)，仅最后拼接栈元素为字符串时是O(n)，整体性能远超原方案。
• 单次遍历无重复扫描：每个字符仅被处理一次，替换后的字符通过循环检查栈顶，自动处理连锁重复问题，无需从头重新遍历。
• 连锁重复处理更高效：例如原方案中cccc需要多次替换（cccc→dd→e），而栈方案会一次性处理所有连续重复，直接得到e。

验证示例 #

输入s='aabbbc'时，栈的处理流程：

1. 压入'a'，下一个'a'与栈顶重复，弹出'a'，替换为'b'，栈为空，压入'b'。
2. 下一个'b'与栈顶重复，弹出'b'，替换为'c'，栈为空，压入'c'。
3. 下一个'b'与栈顶'c'不重复，压入'b'。
4. 下一个'b'与栈顶'b'重复，弹出'b'，替换为'c'；此时'c'与栈顶'c'重复，弹出'c'，替换为'd'，栈为空，压入'd'。
5. 最后'c'与栈顶'd'不重复，压入'c'。
6. 栈最终为['d', 'c']，拼接得到'dc'，与预期结果一致。

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