题解 | #固定字符出现最大次数#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

字符串处理，滑动窗口算法，哈希表的使用。

题目解答方法的文字分析

1. 我们需要统计字符串s中所有长度为k的子串中，t中每个字符的出现次数，并找到其中的最大值作为结果。
2. 为了快速统计字符出现次数，我们使用一个哈希表countMap来存储t中每个字符的出现次数，初始化每个字符的值为0。
3. 使用滑动窗口算法，初始化一个长度为k的窗口，在窗口内统计字符出现次数的总和totalCount。
4. 然后依次滑动窗口，每次右移一个字符，更新窗口内字符的出现次数，并记录最大出现次数maxCount。

例如，假设s="ABCBAB", k=3, t="AB"，我们可以得到以下窗口及对应的字符出现次数：

ABC  --> {'A': 1, 'B': 1} (字符'A'出现1次，字符'B'出现1次)
BCB  --> {'A': 1, 'B': 2} (字符'A'出现1次，字符'B'出现2次)
CBA  --> {'A': 1, 'B': 1} (字符'A'出现1次，字符'B'出现1次)
BAB  --> {'A': 1, 'B': 2} (字符'A'出现2次，字符'B'出现1次)

所以，最大的t中每个字符出现的次数为3。

本题解析所用的编程语言

C++

class Solution {
public:
    int maxCount(string s, int k, string t) {
        // 用于统计字符出现次数的哈希表
        unordered_map<char, int> countMap;
        for (char ch : t) {
            countMap[ch] = 0; // 初始化每个字符出现次数为0
        }
        
        int left = 0; // 窗口左边界
        int maxCount = 0; // 最大出现次数
        int totalCount = 0; // 记录窗口内字符出现次数的总和
        
        // 初始化窗口内字符出现次数
        for (int i = 0; i < k; i++) {
            if (countMap.find(s[i]) != countMap.end()) {
                countMap[s[i]]++;
                totalCount++;
            }
        }
        
        maxCount = totalCount; // 初始化最大出现次数为窗口内字符出现次数的总和
        
        // 滑动窗口
        for (int right = k; right < s.length(); right++) {
            char newCh = s[right];
            if (countMap.find(newCh) != countMap.end()) {
                countMap[newCh]++;
                totalCount++;
            }
            
            char oldCh = s[left];
            if (countMap.find(oldCh) != countMap.end()) {
                countMap[oldCh]--;
                totalCount--;
            }
            
            // 更新最大出现次数
            maxCount = max(maxCount, totalCount);
            
            left++; // 左边界右移
        }
        
        return maxCount;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！