返回目录

题目描述

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

输入描述

第一行有一个子串(1<长度<=100)，只包含大写字母。

第二行为 k的值

输出描述

输出连续出现次数第k多的字母的次数。

示例：

Python算法源码

import re

def main():
    # 从输入中获取字符串和整数k
    s = input()
    k = int(input())

    # 创建一个字符集合和一个空字典用于存储字符和重复次数
    char_set = set(s)
    char_map = {}

    # 对于每个字符，使用正则表达式找到连续出现的次数，并将最大次数存储到字典中
    for c in char_set:
        regex_pattern = c + "+"  # 匹配一个或多个连续的字符
        matches = re.findall(regex_pattern, s)  # 找到所有匹配的子串
        repeat_times = max(len(match) for match in matches)  # 计算最大重复次数
        char_map[c] = repeat_times  # 将字符及其最大重复次数存入字典

    # 将字典中的值按降序排序
    values = sorted(char_map.values(), reverse=True)

    # 如果k小于等于值的数量，返回第k个最大值；否则返回-1
    rt = values[k - 1] if k <= len(values) else -1

    # 输出结果
    print(rt)

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

int main() {
    char str[1001];
    int k = 0;
    scanf("%s", str);
    scanf("%d", &k);

    int charMap[128] = {0}; // 假设ASCII字符范围

    // 统计每个字符出现的次数
    for (int i = 0; str[i] != '\0'; i++) {
        charMap[str[i]]++;
    }

    int values[128];
    int count = 0;
    // 将出现次数非零的字符放入values数组中
    for (int i = 0; i < 128; i++) {
        if (charMap[i] != 0) {
            values[count++] = charMap[i];
        }
    }

    // 对values数组进行降序排序
    qsort(values, count, sizeof(int), compare);

    // 如果k超过了values数组的大小，返回-1；否则返回第k个最大值
    int rt = k > count ? -1 : values[k - 1];
    printf("%d\n", rt);

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next(); // 从输入中获取字符串
        int k = scanner.nextInt(); // 从输入中获取整数k

        Set<Character> charSet = new HashSet<>();
        for (char c : str.toCharArray()) {
            charSet.add(c); // 将字符串中的字符添加到字符集合中
        }

        Map<Character, Integer> charMap = new HashMap<>();
        for (char c : charSet) {
            String regexPattern = c + "+"; // 构建正则表达式，匹配一个或多个连续的字符
            java.util.regex.Pattern pattern = java.util.regex.Pattern.compile(regexPattern);
            java.util.regex.Matcher matcher = pattern.matcher(str);
            int maxRepeatTimes = 0;
            while (matcher.find()) {
                int repeatTimes = matcher.group().length(); // 获取匹配的子串长度
                maxRepeatTimes = Math.max(maxRepeatTimes, repeatTimes); // 计算最大重复次数
            }
            charMap.put(c, maxRepeatTimes); // 将字符及其最大重复次数存入Map中
        }

        List<Integer> values = new ArrayList<>(charMap.values()); // 获取所有最大重复次数的值
        Collections.sort(values, Collections.reverseOrder()); // 对值进行降序排序

        int rt = k > values.size() ? -1 : values.get(k - 1); // 如果k大于值的数量，返回-1；否则返回第k个最大值
        System.out.println(rt); // 输出结果
    }
}