苏州做网站的/爱站工具包官网

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

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

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

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

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1065
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

🏠 连续字母长度

问题描述

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

输入格式

第一行输入一个字符串 $s$，字符串长度满足 $1<|s|\le 10^5$，且只包含大写字母。
第二行输入一个整数 $k$，表示要求的子串长度的排名。

输出格式

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

样例输入

AAAAHHHBBCDHHHH
3

样例输出

2

样例解释

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

数据范围

$1<|s|\le 10^5$
$1\le k\le 26$

题解

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

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

时间复杂度：$O(n\log n)$，其中 $n$ 为字符串 $s$ 的长度。
空间复杂度：$O(1)$。

参考代码

• Python

def solve(s, k):n = len(s)len_arr = [0] * 26i = 0while i < n:j = iwhile j < n and s[j] == s[i]:j += 1c = ord(s[i]) - ord('A')len_arr[c] = max(len_arr[c], j - i)i = jlen_arr.sort(reverse=True)return len_arr[k - 1] if len_arr[k - 1] > 0 else -1s = input().strip()
k = int(input())
print(solve(s, k))

• Java

import java.util.Arrays;
import java.util.Scanner;public class Main {public static int solve(String s, int k) {int n = s.length();int[] lenArr = new int[26];int i = 0;while (i < n) {int j = i;while (j < n && s.charAt(j) == s.charAt(i)) {j++;}int c = s.charAt(i) - 'A';lenArr[c] = Math.max(lenArr[c], j - i);i = j;}Arrays.sort(lenArr);return lenArr[25 - k + 1] > 0 ? lenArr[25 - k + 1] : -1;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s = scanner.nextLine();int k = scanner.nextInt();System.out.println(solve(s, k));}
}

• Cpp

#include <iostream>
#include <string>
#include <algorithm>using namespace std;int solve(string s, int k) {int n = s.length();int lenArr[26] = {0};int i = 0;while (i < n) {int j = i;while (j < n && s[j] == s[i]) {j++;}int c = s[i] - 'A';lenArr[c] = max(lenArr[c], j - i);i = j;}sort(lenArr, lenArr + 26, greater<int>());return lenArr[k - 1] > 0 ? lenArr[k - 1] : -1;
}int main() {string s;int k;cin >> s >> k;cout << solve(s, k) << endl;return 0;
}