【华为OD机试真题】428、连续字母长度 | 机试真题+思绪参考+代码分析（E卷）（C++）

一、标题

   参考：https://sars2025.blog.csdn.net/article/details/139492358
  标题形貌

   ◎ 给定一个字符串，只包罗大写字母，求在包罗同一字母的子串中，长度第k长的子串的长度，雷同字母只取最长的那个子串
  输入输出

   输入
第一行有一个子串(1<长度<=100)，只包罗大写字母
第二行为k的值
输出
输出连续出现次数第k多的字母的次数
  样例1

   输入
AAAAHHHBBCDHHHH
3
输出
2
阐明:
同一字母连续出现的最多的是A和H,出现四次;
第二多的是H, 3次,但是H已经存在4个连续的,故不思量;
下个最长子串是BB，以是终极答案应该输出2
  样例2

   输入
AABAAA
2
输出
1
阐明：
同一字母连续出现的最多的是A,三次;
第二多的还是A,两次,但A已经存在最大连续次数三次,故不思量;
下个最长子串是B,以是输出1
  一、代码与思绪

🧠C++语言思绪

1、起首利用一个unordered map(哈希表)maxCounts来存储每个字符的最长连续出现次数。然后，通过遍历字符串s，记载当前连续
子串的字母和长度。当遇到不同的字符时，将当前字符的出现次数与maxCounts中已存储的最长出现次数进行比力，假如当前字符的出现
次数更长，则更新maxCounts中对应字符的值。
2、接下来，将maxCounts中的最长连续出现次数存入一个vector日中，并利用sort函数Q对vector进行降序排序,
3、末了，根据给定的k值，返回排序后vector中第K个元素的值作为第k长连续子串的长度。假如k值凌驾了vector的长度，则返回-1，表现
没有第k长的连续子串。
✅C++代码

1. #include <iostream>
2. #include <unordered_map>
3. #include <vector>
4. #include <algorithm>
5. #include <string>
7. using namespace std;
9. int findKthLongestSubstring(string s, int k) {
10.     unordered_map<char, int> maxCounts; // 存储每个字母的最长连续出现次数
11.    
12.     char currentChar = s[0]; // 当前连续子串的字母
13.     int currentCount = 1; // 当前连续子串的长度
14.    
15.     for (char c : s.substr(1) + "#") { // 遍历字符串，加上'#'是为了处理字符串最后一个字符的情况
16.         if (c == currentChar) {
17.             currentCount++; // 如果字符与当前字符相同，则增加计数
18.         } else {
19.             if (maxCounts.find(currentChar) == maxCounts.end() || currentCount > maxCounts[currentChar]) {
20.                 maxCounts[currentChar] = currentCount; // 如果字符不同，说明当前连续子串结束，更新最长出现次数
21.             }
22.             currentChar = c; // 重置当前连续子串的字母和长度
23.             currentCount = 1;
24.         }
25.     }
26.    
27.     vector<int> sortedCounts;
28.     for (auto& p : maxCounts) {
29.         sortedCounts.push_back(p.second); // 将最长连续出现次数存入vector
30.     }
31.     sort(sortedCounts.begin(), sortedCounts.end(), greater<int>()); // 将最长连续出现次数按照次数降序排列
32.    
33.     return (k <= sortedCounts.size()) ? sortedCounts[k - 1] : -1; // 根据k值获取第k长的子串长度
34. }
36. int main() {
37.     // 读取输入
38.     string inputString;
39.     getline(cin, inputString);
40.     int k;
41.     cin >> k;
42.    
43.     // 调用函数并输出结果
44.     cout << findKthLongestSubstring(inputString, k) << endl;
45.    
46.     return 0;
47. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。