🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
目录
一、题目描述
给定一个字符串，只包含大写字母，求在包含同一个字母的子串中，长度第 k 长的子串的长度，相同字母只取最长的那个子串。若子串中只包含同一个字母的子串数小于 k，则输出 -1。
1.1 输入描述
第一行有一个字符串（1 < 长度 < 100），只包含大写字母。
第二行有一个数字，表示 k 的值。
1.2 输出描述
输出连续出现次数第 k 多的字母的次数。
1.3 测试样例
1.3.1 示例 1
输入
-
AAAAHHHBBCDHHHH
-
3
输出
2说明：同一字母连续出现的最多的是 A 和 H，4次；第二多的是H，3次，但是 H 已经存在 4 个连续的了，故不再考虑；下个最长的子串是 BB，其长度为 2，所以最终答案应该输出 2。
1.3.2 示例 2
输入
-
AABAAA
-
2
输出
1说明：同一字母连续出现的最多的是A，3次；第二多的还是A，两次，但是A已经出现过了，故不考虑；第二个最长子串是B，它的长度是1，所以输出1
1.3.3 示例 3
输入
-
ABC
-
4
输出
-1说明：只含有 3 个包含同一个字母的子串，小于 k，输出 -1。
1.3.4 示例 4
输入
-
ABC
-
2
输出
1说明：三个子串长度均为 1，所以此时k=1、k=2、k=3 这三种情况均输出 1。
二、解题思路
本题属于简单题，步骤如下所示：
（1）首先，需要统计出连续字符的长度；
（2）然后，根据长度对其逆序排序；
（3）最后，取第 k 长的字符，如果没有则输出 -1。
三、代码实现
代码实现如下所示。
-
#include <iostream>
-
#include <map>
-
#include <vector>
-
#include <algorithm>
-
using
namespace std;
-
-
int consecutiveLetterLength(string str, int k)
-
{
-
int n = str.
length();
-
map<
char,
int>mp;
-
mp[str[
0]] =
1;
-
int num =
1;
-
for (
int i =
1; i < n; ++i) {
-
if (str[i] == str[i -
1]) {
-
num++;
-
}
else {
-
mp[str[i
-1]] = num;
-
num =
1;
-
}
-
}
-
-
if ((
int)mp.
size() < k) {
-
return
-1;
-
}
-
-
vector<pair<
char,
int> > g;
-
for (
auto i = mp.
begin(); i != mp.
end(); ++i) {
-
g.
push_back(
pair<
char,
int>(i->first, i->second));
-
}
-
-
sort(g.
begin(), g.
end(),
-
[](pair<
char,
int> a, pair<
char,
int> b){
return a.second > b.second;});
-
-
return g[k -
1].second;
-
}
-
-
int main()
-
{
-
int k;
-
string str;
-
while (cin>>str>>k) {
-
int ans =
consecutiveLetterLength(str, k);
-
cout<<ans<<endl;
-
}
-
return
0;
-
}
四、时间复杂度
时间复杂度：O(n + m + mlogm)。
在上述代码中，第一个 for 循环时间复杂度为 O(n)，第二个 for 循环时间复杂度为 O(m)，sort 排序的时间复杂度为 O(mlogm)，所以总的时间复杂度为O(n + m + mlogm)，其中 n >= m。
🎈 感觉有帮助记得「一键三连」支持下哦！有问题可在评论区留言💬，感谢大家的一路支持！🤞猿哥将持续输出「优质文章」回馈大家！🤞🌹🌹🌹🌹🌹🌹🤞
转载：https://blog.csdn.net/u011074149/article/details/128172776