查找字符串最长连续streak字符并处理并列排序的Python实现方法

问题描述 #

给定一个由小写字母组成的字符串，要求查找其中最长连续streak的长度，以及对应的所有字母。

输出格式 #

对每个测试用例，输出最长连续streak长度和对应的字母，二者用空格分隔。若存在多个字母的streak长度并列最长，将这些字母按字典序排序后输出。

示例输入输出 #

说明 #

• 输入bacacccbba时，最长streak是ccc，长度为3，对应字母c，输出3 c。
• 输入ccbccbb时，最长streak长度为2，包含cc、cc、bb，对应字母b和c，按字典序输出2 bc。

约束条件 #

• 测试用例数量 1 ≤ t ≤ 10000
• 单个字符串长度 1 ≤ n ≤ 10000
• 字符串仅包含a-z小写字母

现有问题 #

已编写如下代码，仅能输出单个最长streak对应的字母，无法处理并列情况，请问应该如何修改实现？

def longest(seq):
    max_count = 0
    max_char = ""
    prev_char = ""
    
    for current in seq:
        if prev_char == current:
            count += 1
        else:
            count = 1
        if count > max_count:
            max_count = count
            max_char = current
        prev_char = current
    print(max_char,max_count)

longest()

修改方案 #

你原来的代码只存储了单个最长字符，要支持并列场景，把存储最长字符的变量改为集合即可，逻辑调整为：遇到比当前最大值更长的连续序列时，清空集合并加入新的最长字符；遇到和当前最大值长度相等的连续序列时，直接把对应字符加入集合（自动去重），最后把集合按字典序排序输出即可。
修改后的完整代码如下：

def longest(seq):
    max_count = 0
    max_chars = set()
    prev_char = ""
    count = 0
    
    for current in seq:
        if prev_char == current:
            count += 1
        else:
            count = 1
        # 长度超过当前最大值，重置最大值和字符集合
        if count > max_count:
            max_count = count
            max_chars.clear()
            max_chars.add(current)
        # 长度等于当前最大值，加入集合去重
        elif count == max_count:
            max_chars.add(current)
        prev_char = current
    # 按字典序排序后拼接输出
    sorted_chars = ''.join(sorted(max_chars))
    print(max_count, sorted_chars)

# 测试示例
if __name__ == "__main__":
    test_cases = ["bacacccbba", "ccbccbb", "cba", "c"]
    for case in test_cases:
        longest(case)

运行上述代码输出结果和示例完全一致：

3 c
2 bc
1 abc
1 c

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