自己做淘宝客是不是需要建网站,app小程序网站开发是什么,做营销网站,网站开发工具.枫子科技#x1f36d; 大家好这里是清隆学长 #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f497; #x1f… 大家好这里是清隆学长 一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 在线评测链接
https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1065 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁
OJ题目截图 文章目录 在线评测链接OJ题目截图 连续字母长度问题描述输入格式输出格式样例输入样例输出样例解释数据范围题解参考代码 连续字母长度
问题描述
K小姐有一个只包含大写字母的字符串她想知道在所有包含同一字母的子串中长度第 k k k 大的子串的长度是多少。注意对于相同字母只考虑最长的那个子串。
输入格式
第一行输入一个字符串 s s s字符串长度满足 1 ∣ s ∣ ≤ 1 0 5 1 |s| \le 10^5 1∣s∣≤105且只包含大写字母。 第二行输入一个整数 k k k表示要求的子串长度的排名。
输出格式
输出一个整数表示第 k k k 长的子串的长度。如果不存在第 k k k 长的子串则输出 − 1 -1 −1。
样例输入
AAAAHHHBBCDHHHH
3样例输出
2样例解释
在给定的样例中同一字母连续出现次数最多的是 A A A 和 H H H均为 4 4 4 次。第二多的是 H H H有 3 3 3 次连续出现但由于 H H H 已经有了更长的子串因此不予考虑。下一个最长的子串是 B B BB BB长度为 2 2 2。因此最终答案为 2 2 2。
数据范围 1 ∣ s ∣ ≤ 1 0 5 1 |s| \le 10^5 1∣s∣≤105 1 ≤ k ≤ 26 1 \le k \le 26 1≤k≤26
题解
本题可以通过统计每个字母出现的最长连续子串的长度然后对这些长度进行排序来解决。具体步骤如下
遍历字符串 s s s统计每个字母出现的最长连续子串的长度并用一个长度为 26 26 26 的数组 l e n len len 来存储其中 l e n [ i ] len[i] len[i] 表示字母 i i i 出现的最长连续子串的长度。对数组 l e n len len 进行降序排序。判断排序后的数组 l e n len len 中第 k − 1 k-1 k−1 个元素下标从 0 0 0 开始是否为 0 0 0如果为 0 0 0说明不存在第 k k k 长的子串输出 − 1 -1 −1否则输出 l e n [ k − 1 ] len[k-1] len[k−1] 即可。
时间复杂度 O ( n log n ) O(n \log n) O(nlogn)其中 n n n 为字符串 s s s 的长度。 空间复杂度 O ( 1 ) O(1) 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(reverseTrue)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 algorithmusing 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, greaterint());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;
}
