连续字母长度 - 华为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。特此说明，避免歧义。

题解

解题思路：

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