原题链接

如果直接使用双指针，没有单调性，可以尝试先将原问题分成几个子集，子问题有单调性可以使用双指针。

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
30
31
class Solution {
public:
    int K;
    unordered_map<char, int> cnt;
    void add(char c, int& x, int& y) {
        if(!cnt[c]) x++;
        cnt[c]++;
        if(cnt[c] == K) y++;
    }
    void del(char c, int& x, int& y) {
        if(cnt[c] == K) y--;
        cnt[c]--;
        if(!cnt[c]) x--;
    }
    int longestSubstring(string s, int _k) {
        K = _k;
        int res = 0;
        // 枚举区间中最多包含的不同字符的数量这个条件
        for(int k=1;k<=26;k++) {
            cnt.clear();
            // x 表示不同字符的数量
            // y 表示满足要求的字符的数量
            for(int i=0,j=0,x=0,y=0;i<s.size();i++) {
                add(s[i], x, y);
                while(x>k) del(s[j++], x, y);
                if(x==y) res = max(res, i-j+1);
            }
        }
        return res;
    }
};