华为od机试真题：连续字母长度(Python)

题目描述

给定一个字符串，只包含大写字母，求在包含同一字母的子串中，长度第 k 长的子串的长度，相同字母只取最长的那个子串。

输入描述

第一行有一个字符串(1<长度≤100000)，只包含大写字母 第二行为 k 的值

输出描述

输出连续出现次数第 k 多的字母的次数，当第k多的字母的次数不存在时，请输出-1

示例1

输入：
AAAAHHHBBCDHHHH
3

输出：
1

说明：
同一字母连续出现的最多的是 A 和 H ，四次 第二多的是 H，3 次，但是H 已经存在 4 个连续的，故不考虑下个最长子串是 BB，所以最终答案应该输出2.

示例2

输入：
AABAAA
2

输出：
1

说明：
同一字母连续出现的最多的是 A，三次， 第二多的还是A，两次，但A已经存在最大连续次数三次 故不考虑; 下个最长子串是 B，所以输出 1。

示例3

输入：
ABC
4

输出：
-1

说明：
只含有 3 个包含同一字母的子串，小于 k,输出 −1。

示例4

输入：
ABC
2

输出：
1

说明：
三个子串长度均为1，所以此时 k=1，k=2，k=3 这三种情况均输出 1。特此说明，避免歧义。

题解

解题思路：

1. 遍历字符串，统计相同字母的连续子串的长度。
2. 使用数组 cnt 记录每个字母最长子串的长度，其中 cnt[i] 表示字母 A + i 的最长子串长度。
3. 使用集合 scnt 进行去重处理，记录所有不同的子串长度。
4. 判断集合 scnt 的大小，如果小于 k，则输出 -1，表示不存在第 k 多的字母。
5. 否则，将数组 cnt 排序，输出第 26 - k 个元素，即第 k 多的字母的最长子串长度。

Python

# 相同字母取最长的那个子串长度
# cnt[1] 表示 'B' 最长的子串长度
cnt = [0] * 26

# 输入字符串和k值
s = input()
k = int(input())

n = len(s)
i = 0
while i < n:
    j = i + 1
    while j + 1 < n and s[j] == s[i]:
        j += 1

    idx = ord(s[i]) - ord('A')
    cnt[idx] = max(cnt[idx], j - i)

    i = j

# 去重处理
scnt = set([cnt[i] for i in range(len(cnt)) if cnt[i] > 0])

if len(scnt) < k:
    print(-1)
else:
    # 排序长度
    cnt.sort()
    print(cnt[26 - k])

2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏