题目:1297. 子串的最大出现次数

时间:2024-10-13 16:42:07

> Problem: 1297. 子串的最大出现次数

题目:1297. 子串的最大出现次数

题目描述

给定一个字符串 s,要求找到满足以下条件的任意子串的出现次数,并返回该子串的最大出现次数:

  1. 子串中不同字母的数目必须小于等于 maxLetters
  2. 子串的长度必须在 minSizemaxSize 之间。

示例:

  • 示例 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 中,找到满足以下条件的子串,并返回其出现的最大次数:

  1. 子串中不同字母的数目小于等于 maxLetters
  2. 子串的长度必须在 [minSize, maxSize] 范围内。

难点在于我们需要找到出现次数最多的子串,同时需要控制子串长度和字母种类数量。

解题思路

这个问题的核心是通过滑动窗口遍历所有可能的子串,并统计每个子串的出现次数。为了解决这个问题,主要有几个关键步骤:

  1. 滑动窗口提取子串:我们遍历字符串,逐个提取长度为 minSize 的子串,检查这些子串是否满足不同字母数小于等于 maxLetters 的要求。

  2. 统计子串出现次数:使用哈希表 unordered_map 统计每个符合条件的子串的出现次数。

  3. 记录出现次数最多的子串:在遍历过程中,我们会实时更新子串的最大出现次数。

关键点解释

在实际实现中,我们直接使用 minSize 而不是遍历从 minSizemaxSize 所有可能的长度。这是因为:

  1. 最小长度子串更容易符合 maxLetters 限制:较短的子串往往更容易满足字母种类不超过 maxLetters 的限制。如果使用较长的子串,很可能会包含更多的不同字母,无法满足条件。
  2. 简化计算复杂度:遍历多个长度会显著增加计算复杂度,而实际上较长子串不会比较短子串出现更多次,直接使用 minSize 能够降低时间复杂度。
  3. 长度为 minSize 的子串已经覆盖所有可能的子串:即便存在满足 maxLetters 条件的较长子串,它们也必然包含短子串的一部分,直接检查 minSize 长度已经能够找到符合条件的子串。

算法步骤

  1. 初始化变量

    • 使用一个哈希表 freqMap 来存储每个子串的出现次数。
    • 使用变量 maxFreq 来记录最大出现次数。
  2. 遍历字符串

    • 遍历字符串 s,从每个位置 i 开始,提取长度为 minSize 的子串。
    • 使用 unordered_set 统计子串中的不同字母数,如果满足 maxLetters 的要求,则记录该子串的出现次数。
  3. 更新最大出现次数

    • 每次有符合条件的子串时,更新 maxFreq,确保记录下出现次数最多的子串。
  4. 返回结果:最终返回 maxFreq,即最大出现次数。

代码实现

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        unordered_map<string, int> freqMap; // 存储子串的频率
        int maxFreq = 0; // 记录最大出现频率

        // 遍历所有长度为 minSize 的子串
        for (int i = 0; i <= s.size() - minSize; ++i) {
            string subStr = s.substr(i, minSize); // 提取长度为 minSize 的子串
            unordered_set<char> 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