题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个字符串，求满足要求的子串中，出现最多的次数。该要求为 1. 内部的字母数量小于 maxLetters；2. 整个字符串的长度在 minSize 和 maxSize 之间（闭区间）。

思路分享

  • 该题的难度在于干扰项 maxSize，由于求子串尽可能多的出现，所以该子串的长度必然越小越好，就是 minSize。

  • 就是定长滑动窗口(【Leetcode Daily】1456定长子串中元音的最大数目)，有了个字母数量不大于 maxLetters 的限制，再用哈希统计满足要求字符串出现的次数即可。

代码解答（强烈建议自行解答后再看）

  • 陆爻齐的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        vector<int> rec_letter(26, 0); // 记录窗口内个字母的计数
        int count_letter = 0; // 窗口内字幕数目的计数
        
        unordered_map<string, int> rec_str;
        int max_count_str = 0; // 记录子串出现的最大数目

        string tmps;
        for (int i = 0; i < s.size(); i++) {
            tmps += s[i];
            rec_letter[s[i]-'a']++;
            if (rec_letter[s[i]-'a']==1) count_letter++;

            if (i < minSize-1) continue; // 窗口大小

            if (count_letter <= maxLetters) {
                rec_str[tmps]++;
                max_count_str = max(rec_str[tmps], max_count_str);
            }

            rec_letter[tmps[0]-'a']--;
            if (rec_letter[tmps[0]-'a']==0) count_letter--;
            tmps.erase(tmps.begin());
        }
        return max_count_str;
    }
};