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

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

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

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

题目描述

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

  1. 子串中不同字母的数目必须小于等于 maxLetters。
  2. 子串的长度必须在 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 中，找到满足以下条件的子串，并返回其出现的最大次数：

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

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

解题思路

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

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

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

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

关键点解释

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

  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。

相关文章