连续字母长度 - 华为OD统一考试(D卷)
OD统一考试(D卷)
分值: 100分
题解: Java / Python / C++
题目描述
给定一个字符串,只包含大写字母,求在包含同一字母的子串中,长度第 k
长的子串的长度,相同字母只取最长的那个子串。
输入描述
第一行有一个字符串(1<长度≤1000001<长度≤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。特此说明,避免歧义。
题解
解题思路:
- 遍历字符串,统计相同字母的连续子串的长度。
- 使用数组
cnt
记录每个字母最长子串的长度,其中cnt[i]
表示字母A + i
的最长子串长度。- 使用集合
scnt
进行去重处理,记录所有不同的子串长度。- 判断集合
scnt
的大小,如果小于k
,则输出-1
,表示不存在第k
多的字母。- 否则,将数组
cnt
排序,输出第26 - k
个元素,即第k
多的字母的最长子串长度。
Java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
int k = in.nextInt();
// 相同字母取最长的那个子串长度
// cnt[1] 表示 'B' 最长的子串长度
int[] cnt = new int[26];
int n = s.length();
for (int i = 0; i < n; ) {
int j = i + 1;
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
华为OD机试题库&题解2024 文章被收录于专栏
华为OD机考(C卷、D卷)题库(绝对都是原题,命中率 95%以上。),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。