如何高效拆分字符串，仅保留连续重复两次的字符实例？

需求明确 #

给定字符串 s = 'aaabcdedddd'，拆分规则如下：

• 单个字符直接保留（如示例中的b、c、d、e）
• 连续2个相同字符保留为一个元素（如aa）
• 连续3个相同字符拆分为2个+1个的组合（如aaa→['aa', 'a']）
• 连续≥4个相同字符，优先拆分为多个2个的组，若剩余1个则单独保留（如dddd→['dd', 'dd']，aaaaa→['aa', 'aa', 'a']）

高效实现方式（Python） #

可以通过一次遍历统计连续字符长度的方式实现，时间复杂度为O(n)（线性时间复杂度），效率较高：

def split_repeating_chars(s):
    if not s:
        return []
    result = []
    current_char = s[0]
    count = 1
    for char in s[1:]:
        if char == current_char:
            count += 1
        else:
            # 处理当前连续字符组
            while count > 0:
                if count >= 2:
                    result.append(current_char * 2)
                    count -= 2
                else:
                    result.append(current_char)
                    count -= 1
            current_char = char
            count = 1
    # 处理最后一组未完成的字符
    while count > 0:
        if count >= 2:
            result.append(current_char * 2)
            count -= 2
        else:
            result.append(current_char)
            count -= 1
    return result

# 测试示例
s = 'aaabcdedddd'
print(split_repeating_chars(s))  # 输出: ['aa', 'a', 'b', 'c', 'd', 'e', 'dd', 'dd']

代码说明 #

1. 初始化变量记录当前字符和连续出现次数，遍历字符串时同步更新计数
2. 当遇到不同字符或遍历结束时，对当前连续字符组按规则拆分：
   • 剩余计数≥2时，优先生成2字符的元素，计数减2
   • 剩余1个字符时，单独生成单个字符元素
3. 整个过程仅遍历字符串一次，拆分逻辑简单直接，避免了复杂正则匹配或多次遍历的额外开销

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