泊头市建设网站,网站排名突然掉了怎么回事,做灯箱片的设计网站,进京服务的链接 Problem: 1297. 子串的最大出现次数
题目#xff1a;1297. 子串的最大出现次数 题目描述
给定一个字符串 s#xff0c;要求找到满足以下条件的任意子串的出现次数#xff0c;并返回该子串的最大出现次数#xff1a;
子串中不同字母的数目必须小于等于 maxLetters。… Problem: 1297. 子串的最大出现次数
题目1297. 子串的最大出现次数 题目描述
给定一个字符串 s要求找到满足以下条件的任意子串的出现次数并返回该子串的最大出现次数
子串中不同字母的数目必须小于等于 maxLetters。子串的长度必须在 minSize 和 maxSize 之间。
示例 示例 1 输入s aababcaab, maxLetters 2, minSize 3, maxSize 4
输出2
解释子串 aab 在字符串中出现了 2 次且符合所有要求。示例 2 输入s aaaa, maxLetters 1, minSize 3, maxSize 3
输出2
解释子串 aaa 在字符串中出现了 2 次且满足不同字母不超过 1 个。示例 3 输入s aabcabcab, maxLetters 2, minSize 2, maxSize 3
输出3
解释子串 ab、bc 和 ca 都出现了 3 次满足条件。题目分析
题目要求在给定字符串 s 中找到满足以下条件的子串并返回其出现的最大次数
子串中不同字母的数目小于等于 maxLetters。子串的长度必须在 [minSize, maxSize] 范围内。
难点在于我们需要找到出现次数最多的子串同时需要控制子串长度和字母种类数量。
解题思路
这个问题的核心是通过滑动窗口遍历所有可能的子串并统计每个子串的出现次数。为了解决这个问题主要有几个关键步骤 滑动窗口提取子串我们遍历字符串逐个提取长度为 minSize 的子串检查这些子串是否满足不同字母数小于等于 maxLetters 的要求。 统计子串出现次数使用哈希表 unordered_map 统计每个符合条件的子串的出现次数。 记录出现次数最多的子串在遍历过程中我们会实时更新子串的最大出现次数。
关键点解释
在实际实现中我们直接使用 minSize 而不是遍历从 minSize 到 maxSize 所有可能的长度。这是因为
最小长度子串更容易符合 maxLetters 限制较短的子串往往更容易满足字母种类不超过 maxLetters 的限制。如果使用较长的子串很可能会包含更多的不同字母无法满足条件。简化计算复杂度遍历多个长度会显著增加计算复杂度而实际上较长子串不会比较短子串出现更多次直接使用 minSize 能够降低时间复杂度。长度为 minSize 的子串已经覆盖所有可能的子串即便存在满足 maxLetters 条件的较长子串它们也必然包含短子串的一部分直接检查 minSize 长度已经能够找到符合条件的子串。
算法步骤 初始化变量 使用一个哈希表 freqMap 来存储每个子串的出现次数。使用变量 maxFreq 来记录最大出现次数。 遍历字符串 遍历字符串 s从每个位置 i 开始提取长度为 minSize 的子串。使用 unordered_set 统计子串中的不同字母数如果满足 maxLetters 的要求则记录该子串的出现次数。 更新最大出现次数 每次有符合条件的子串时更新 maxFreq确保记录下出现次数最多的子串。 返回结果最终返回 maxFreq即最大出现次数。
代码实现
class Solution {
public:int maxFreq(string s, int maxLetters, int minSize, int maxSize) {unordered_mapstring, int freqMap; // 存储子串的频率int maxFreq 0; // 记录最大出现频率// 遍历所有长度为 minSize 的子串for (int i 0; i s.size() - minSize; i) {string subStr s.substr(i, minSize); // 提取长度为 minSize 的子串unordered_setchar uniqueLetters(subStr.begin(), subStr.end()); // 计算子串中不同字母数// 如果满足不同字母数 maxLetters 的条件if (uniqueLetters.size() maxLetters) {freqMap[subStr]; // 记录子串出现次数maxFreq max(maxFreq, freqMap[subStr]); // 更新最大出现频率}}return maxFreq; // 返回最大出现次数}
};详细解析 字符串切割每次通过 substr 提取长度为 minSize 的子串这样可以保证我们只处理符合要求长度的子串。 字母去重统计我们使用 unordered_set 来去重统计子串中的不同字母这样可以快速判断该子串是否符合 maxLetters 的限制。 频率统计通过 unordered_map 来记录子串出现的次数。对于每一个符合要求的子串都会将其频率加 1。 结果输出每次找到符合要求的子串后我们实时更新最大频率 maxFreq确保最终得到最大出现次数的子串。
时间复杂度 时间复杂度为 O(n * minSize)其中 n 为字符串 s 的长度。因为我们需要遍历每个长度为 minSize 的子串并进行去重和统计操作。 空间复杂度为 O(n)主要用于存储子串的频率哈希表和去重的 unordered_set。
