连续字母长度 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 100分

题解： Java / Python / C++

华为od真题

题目描述

给定一个字符串，只包含大写字母，求在包含同一字母的子串中，长度第 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;
            while (j + 1 < n && s.charAt(j) == s.charAt(i)) j++;

            int idx = s.charAt(i) - 'A';
            cnt[idx] = Math.max(cnt[idx], j - i);

            i = j;
        }

        // 去重处理
        Set<Integer> scnt = new HashSet<>();
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) {
                scnt.add(cnt[i]);
            }
        }

        if (scnt.size() < k) {
            System.out.println(-1);
        } else {
            // 排序长度
            Arrays.sort(cnt);
            System.out.println(cnt[26 - 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])

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int k;
    cin >> s;
    cin >> k;

    // 相同字母取最长的那个子串长度
    // cnt[1] 表示 'B' 最长的子串长度
    int cnt[26] = {0};

    int n = s.length();
    for(int i=0;i<n;){
        int j = i + 1;
        while(j + 1 < n && s[j] == s[i]) j++;

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

        i = j;
    }

    // 去重处理
    set<int> scnt;
    for(int i=0;i<26;i++){
        if(cnt[i] > 0) scnt.insert(cnt[i]);
    }

    if(static_cast<int>(scnt.size()) < k){
        cout << -1 << endl;
    }else{
        // 排序长度
        sort(cnt, cnt + 26);
        cout << cnt[26 - k] << endl;
    }

    return 0;
}