395.至少有 K 个重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/

• 题目说了只有小写字母，那么就利用题目本身的限制，

• 每次尝试的时候把它含有的字符种类限制死

利用窗口

• R往右动的情况

  • 1）种类不足
  • 2） 每种字符没有凑齐 K个

• 如果R一直往右直到越界都没形成一个窗口，说明无答案

• R什么时候停？ 种类超了

过个例子

R停，看达标不， 达标， 收集一个答案， 然后左边缩一个

R扩不动，不达标，不收集答案

..
总而言之，只有种类够，次数也够才收集答案

没有用滑动窗口加速的解法

 public int longestSubstring1(String s, int k) {
        char[] str = s.toCharArray();
        int N = str.length;
        int max = 0;
        for (int i = 0; i < N; i++) {
            int[] count = new int[256];
            int collect = 0;
            int satisfy = 0;
            for (int j = i; j < N; j++) {
                if (count[str[j]] == 0) {
                    collect++;
                }
                if (count[str[j]] == k - 1) {
                    satisfy++;
                }
                count[str[j]]++;
                if (collect == satisfy) {
                    max = Math.max(max, j - i + 1);
                }
            }
        }
        return max;
    }

优化之后

//滑动窗口优化加速
    public int longestSubstring2(String s, int k) {
        char[] str = s.toCharArray();
        int N = str.length;
        int max = 0;
        for (int require = 1; require < 26; require++) { //字母种类
            int[] count = new int[26];
            int collect = 0; //目前窗口内收集了几种字符了
            int satisfy = 0; //目前窗口内出现次数>=k次的字符，满足了几种
            int R = -1;   // 窗口右边界
            for (int L = 0; L < N; L++) { // L要尝试每一个窗口的最左位置
                // [L..R]  R+1
                while (R + 1 < N && !(collect == require && count[str[R + 1] - 'a'] == 0)) {
                    R++;
                    if (count[str[R] - 'a'] == 0) {
                        collect++;
                    }
                    if (count[str[R] - 'a'] == k - 1) {
                        satisfy++;
                    }
                    count[str[R] - 'a']++;
                }
                // R扩不动了, 看达标不
                if (satisfy == require) {
                    max = Math.max(max, R - L + 1);
                }
                if (count[str[L] - 'a'] == 1) {
                    collect--;
                }
                if (count[str[L] - 'a'] == k) {
                    satisfy--;
                }
                count[str[L] - 'a']--;
            }
        }
        return max;
    }