最新华为OD机试真题-连续字母长度(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

连续字母长度(100分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🏠 连续字母长度

问题描述

K小姐有一个只包含大写字母的字符串，她想知道在所有包含同一字母的子串中，长度第 大的子串的长度是多少。注意，对于相同字母，只考虑最长的那个子串。

输入格式

第一行输入一个字符串 ，字符串长度满足 ，且只包含大写字母。 第二行输入一个整数 ，表示要求的子串长度的排名。

输出格式

输出一个整数，表示第 长的子串的长度。如果不存在第 长的子串，则输出 。

样例输入

AAAAHHHBBCDHHHH
3

样例输出

2

样例解释

在给定的样例中，同一字母连续出现次数最多的是 和 ，均为 次。第二多的是 ，有 次连续出现，但由于 已经有了更长的子串，因此不予考虑。下一个最长的子串是 ，长度为 。因此，最终答案为 。

数据范围

题解

本题可以通过统计每个字母出现的最长连续子串的长度，然后对这些长度进行排序来解决。具体步骤如下：

1. 遍历字符串 ，统计每个字母出现的最长连续子串的长度，并用一个长度为 的数组 来存储，其中 表示字母 出现的最长连续子串的长度。
2. 对数组 进行降序排序。
3. 判断排序后的数组 中第 个元素（下标从 开始）是否为 ，如果为 ，说明不存在第 长的子串，输出 ；否则，输出 即可。

时间复杂度：，其中 为字符串 的长度。 空间复杂度：。

参考代码

• Python

def solve(s, k):
    n = len(s)
    len_arr = [0] * 26
    i = 0
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        c = ord(s[i]) - ord('A')
        len_arr[c] = max(len_arr[c], j - i)
        i = j
    
    len_arr.sort(reverse=Tru